Unlock (UVa 11999 World Finals Warmup 2011 2)
問題
W*Hの盤面に図のように順番に番号を付け、1番から順に左上から順に並べ直す作業をする。この作業を何回やれば数値が1から順に並ぶか答えよ。
1<=W,H<=200
与えられたW,Hでは、答えが存在する任意の盤面で答えが2*10^18以下になる
解法
まずパーミュテーションを生成する。これが終わったら次に、それぞれの巡回群のサイズを求める。サイズが求め終わったら、次にその巡回群の最初の数値を何回スライドさせれば目的の箇所に到達できるか調べる。次にその巡回群の中の数値をそれぞれ最初の物と同じ分だけ動かした時にちゃんと目的の位置に合わさってるかチェックする。最後に求めた全ての巡回群のサイズとスライドさせる回数を中国人剰余定理を使って合体させてやれば答えは出る。
巡回群の中の数値を愚直に全部回してチェックしてるとTLEするし、中国人剰余定理を使う時に互いに素で無い場合があるし、中国人剰余定理の中で掛け算を使うとオーバーフローが発生したりとかなり落とし穴があるので注意して実装すること。
