No.101 ぐるぐる!あみだくじ!
No.101 ぐるぐる!あみだくじ! - yukicoder
- 最初計算量が見積もれなかった。
- 各 x の周期の最小公倍数が全体の周期になる。
- まあ言われればわかるんだけど...、こういうのをぱっと思いつけるようになりたい。
class GruGruAmidakuji { public: void solve(void) { int N,K; cin>>N>>K; // F[i] := i を入力するとあみだくじをたどって F[i] に到達する vector<int> F(N); iota(RANGE(F),0); REP(i,K) { int x,y; cin>>x>>y; --x,--y; // 棒があるとそこで入力が交換される swap(F[x],F[y]); } // // F^s(x) = F*F*...*F(x)=x (all x) なる最小の s を探せば良い // // 各 xi に対して F(xi)^si = xi なる最小の si を求めてそれらの最小公倍数が全体の周期になる。 // 一つの xi に対しては周期は最大 N になるはず ll ans = 1; REP(i,N) { int x = i; FOR(s,1,N+1) { x = F[x]; if (x == i) { ans = lcm(ans,(ll)s); break; } } } cout<<ans<<endl; return; } };