566.1

かなり良く作られてるセット。

250

線分がいくつか与えられるので、端点をどのように移動させても線分が交差しないように線分を取り除く方法は何通りあるか答えよ、という問題。

全部の線分が一つの頂点を共有するケースと、三角形が一つあるケース、線分がないケースを全部数え上げれば良いらしい。

500

円周上にN個の点がある。向きを自由に選んで良いので、K回目の移動ではK個先の点に移動するとき、全部でM回移動する場合に最初の点に戻ってくる方法は何通りあるか答えよ、という問題。

開始点はどれでも同じ、というかN個の点を識別する手段はない。つまり、どの状態であっても移動先との距離で遷移する方法の数は決まる。後は漸化式を行列乗算に落としてやって、前述の特性を使って行列乗算を高速にやればおしまい。

1000

円周上にN個の点が等間隔に置かれている。M個の点があるので、それを囲うようにN個の点を頂点とする多角形を描く方法は何通りあるか答えよ、という問題。

思いつく方法がどれも囲った点の状態を覚えておかないといけない時点でムリゲー。