CF #485
Um_nik回
A
制約がO((N+M)K)と言っている
→ K回幅優先できそうだしこれだろう
→ 一応sortじゃなくてnth_element使っとくか(logが消えます)
B
オッ乱択
→ ランダムスワップの回数が増えるとどうなる？
→ a[i] = iの要素数が減っていくんじゃないか？
→ とりあえず実験してみるか
→ いや3nはともかく7n+1ってなんだよ
→ なんで7n回じゃないんだ？+1回でなんか本質的に変わるのか？偶奇？
→ そういえばswapは置換なので偶置換奇置換という概念があった
C
こういう2n頂点4n辺(n=20ぐらい)のグラフを仮想的に考えてやるやつは，結構ロシア合宿とかで見る
→ 大体本質的に見る必要のある辺だけ注目したり，追加頂点を作って辺をまとめたりする
→ 今回は後者っぽい？うまくまとめたいね
→ 00110から辺を貼れる頂点は??00?
→ ?が出てきたので高速ゼータ変換系を疑う，??001みたいに?を途中まで1に変換したやつを状態に持つ？
→ できそうだけど，よく考えると状態数n * 2nってメモリの確保すらしんどくないか？
→ ということは状態数O(2n)のままでなんとかなるんだろう
状態数O(2n)でなんとかやりたい → ??00?は流石に用意しないとどうしようもなくない？ → ?0の混合だけでなんとかなる？ → (??00? -> 0?00?, ?000?, ??000, 11001)みたいな遷移かー
D
だいたいlogとか考えると解ける？
→どうやっても3xとの比較が必要じゃない？
→やめるか
E
gcd(a_i, x)の積
→ a_i, xの値が107と中途半端
→ 約数の個数系？
まずパスクエリをどう分解する？
→ 逆元は？存在するね
→ オイラーツアー？
→ オイラーツアーとか木を状態持ちながらdfsとかでいいね
整理
→ 数が追加されたり削除されたりクエリが飛んできたりする
→ 適時gcd(a_i, x)の積を求めよ
数が追加された時，クエリxの答えはどうなる？
→ 6を追加すると？12を追加すると？4を追加すると？(実験)
→もしかして素因数ごとに分解するだけ？
実装が大変
→ところでジャッジ壊れてない？
→うーんもうめちゃくちゃ
