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を追加すると?(実験)
 →もしかして素因数ごとに分解するだけ?

実装が大変
→ところでジャッジ壊れてない?
 →うーんもうめちゃくちゃ