ABDの3完。昨日と展開は似ている。今日は頭の悪さばかりを感じた。昨日よりは調子が悪かったと思う。
A - mod M
答えは1か2（M=2とすれば2種類以下になる）。種類数を最小にするMを選んだとき、Mで割ったあまりは全部同じということで、どんなペアも差がmod Mで0になると気づく。最小のA_iをとって全部からそれを引いてみる。GCDが2以上なら、Ｍとしてそれを選べば答えは1。そうでないときは2か？ここからかなり考えて証明できず、もし間違っていてもペナで時間を買ったほうがいいと判断し提出、WA。
GCDが1なのに答えが1のことがあるってことだ。少し考えて、GCDが0のケースを思いつく。GCDとしての0って全ての素因数を持ったクソデカ数だからこれは気づきにくい。今考えると、GCDが1かどうかで考えればよかったな。
改めて考える。そもそもA全体に同じ数を足しても状況は変化しない（Mで割ったあまりも同じだけ動く）。つまりAのうち少なくとも一つが0だとしてよくて、その0は何で割ったあまりも0だから他の要素もMで割り切れる必要がある、よってMはAの公約数である必要がある。
B - dp
解法がDPなのか気になるが、まあ先頭から決めていきたくなる。最初の文字をdにできるか、できるならその上で次の文字をdにできるか。初めてpが現れたとき、選ぶ区間はそこを含んでいる必要がある。操作後、できるだけdを連続させたいが、ここで区間の先頭をそのpより前にすると、操作後のdの連続数が余計に必要になってしまう（pがもっと連続して終わる区間を選ぶ必要があるがそんなものがあれば元の位置からそこまでを区間として選んでる）。よって、感覚ではわからないのだが、区間の先頭はそのpとしてよい。計算量が、制約は2乗っぽく見えるけど、考えていると1乗や3乗ばかりがありそうでつらかった。
わからなくてCと交互にやっていたが、Cがわからないので戻ってきた。区間の終わりはpが一番多く並んだ場所が候補になる。pの連続数でインデックスをvectorのvectorに入れていく。一番連続数が大きい候補を全探索。これで2乗になった。提出してWA。どう見ても正しいのでつらかった。時間がかかっているので、これ以上無駄な時間を過ごさないように順位表を見た。区間内が全部pでありかつ区間の直後がdであるケースを見落としていた。このときは操作後のdの連続数が区間末尾のpの連続数より大きくなる。ていうか区間の先頭は最初のpの位置で決まったのだから、単に全探索すればよかった。そのように実装してWA。区間の終わりの位置をN未満までしか見てなかったが、半開区間なのでNも含めなくてはいけなかった。これでAC。ズタボロ。
C - Lights Out on Tree
Q=1なら簡単で、上から、操作しなければならない場所を操作していくだけ。Mが小さいときにどうやって高速化できるかという問題。M=1なら、そこを操作して、子を操作して戻すだけ。ただ、100個とかあるときにどうなっているか。どの部分木に入ってるかもわからんし。自分も直接の子の一つも点灯してるなら状況が変わりそう。他の子孫の点灯してるやつが、その中に入っているかどうかで話が変わってくる。解けそうにない。
（追記）点灯している1個を消す操作は、自分と自分の子に対するもの。直接の子でない子孫が点灯していた場合、祖先が2回操作されるから影響がない。え。なんで気づかないというか、なんとなくのイメージで探ることもしてなかったってこと？親子で点灯していた場合、親から見ると子の操作が1個減って、子から見ると自分への操作が1個減る。実装は、入力通りに親を記録しておいて、子をカウント。クエリは、予め長さNの-1で初期化したvectorを用意しておいて、頂点番号のところにクエリ番号を入れる（こうすればlogは付かない）。親が頂点集合に入っていたら2を引く。
D - mod M Game
AB遅解きでCが解けそうにないので、Dに賭けましょう（改めてCを考えてみたい気持ちもあったが）。順位表で誰が解けてるか見てやや相性悪そうとは思ったが通してる人数自体は多い。Nが偶数のときを考えようとしていたが、とりあえず入力受け取るところまで書くかと思い書いていると、そもそも2*N個だったことにようやく気づく（実装は証明のような頭の使い方をするのでこういうのに気づきやすい）。
Bobが勝つケースを考えると、サンプル2のように全部の数が偶数個ずつあればAliceと同じものを選んでいけば勝てる。さすがにこれで正解というわけではないだろう。他にBobが勝つケースがないか探してみる。特に、合計が同じにならないケース。M=5で考えて無理そうだったので、modがわかりやすいM=10で考えていると、7 2 8 3という差が5のペアが2つあるケースを思いつく。これはBobが勝てる。毎回modの差を5だけ変化させることができるのでそれが偶数回なら勝ち。じゃあMの約数で同様のことができる？特に、Mが奇数のときにBobの勝ち筋がある？少し試すと、約数が2より大きいときはAliceに回避されてしまう。2以外の約数は同様の方法では使えない。もう時間もないので、これ以外にBobの勝ち筋はないとして実装する。同じ数で合わせるのとM/2違いのペアで合わせるのと2種類あるけど、少し試して同じ数で合わせるのを優先して問題なさそう。mapで各数が何個あるか調べ、個数をmod 2にする。Mが偶数ならM/2未満のものについて自分よりM/2大きいものがあれば両方0にする（ペアを取り除いたので高々1個しかない）。mapの表面しかいじってないからイテレータは壊れないはず。実現したいことは固まってるのにコードに落とすのけっこうむずくてドキドキしてた。こういう実装力はARCの本質という気がする。最後、何も残ってなくてM/2ペアを作った個数が偶数ならBobの勝ち。そうでないときはたぶんAliceの勝ち。AC。
こんなずっこい取り方して黄パフォに届かないのやべえな。
F - 998244353 → 1000000007
（追記）モンゴメリ乗算というヒントを得て簡単そうだと思いやってみたが全然できなかった。まず998244353で割る処理が書けない。解説を見て、あまりを引いたあとでmod 2^64での逆元を掛ければいいと知る。rem命令ってそう使うのね。あと、最上位ビットとかを得る方法があればいいのだが、わからない。解説を見ると、1000000007以上かの判定をする方法が書いてあった（1000000007でなくても使える方法）。1000000007を引いて負になるなら2^64が足されるからmod 998244353での値の振る舞いが変わる。ここでもremを使っている。普通のコンピュータを相手にしてるときは使わない発想なのでこれは相当思いつかない。998244353と1000000007にばかり気を取られてしまうが、2^64もあった。ここの処理はかなりややこしかった。解説を見たところ以外にも、簡単には処理できない問題がいくつも現れていた。モンゴメリ乗算自体は今も全然わかってなくて、C++コンパイラの除算の最適化で使われる方法あるいはACLのmodintで使われている方法が頭にあったうえで解法ツイートを見て大まかな方針が立ったという感じ。
具体的な解法。引き算は符号反転して足せばいい。符号反転は2^64-1（~0ULLと書ける）を掛ければいい。逆元はextgcdを貼るが、数が2^64と大きいので1段目は手で書いて2段目からextgcdに投げる。逆元を掛ければ1になる（当たり前）。方針としては、A*Bを1000000007で割った商を多少誤差があってもいいので求めたい。998244353で割ることはできるので、A*B/998244353*(998244353^2/1000000007)/998244353として求める（除算は切り捨て）。こうして求めた値は、正しい商より大きくなることはない（切り捨てているので）（あんま考えてなかったけど、正確には丸める前の値以下であることが保証され商はそういう整数の中で最大のものだからOK）。どのくらい小さくなりうるかだが、10^9程度同士の積をとるときに高々1ずつ小さいなら2*10^9程度、その後の割り算でこの誤差も割られるので、割り算の1未満の誤差と合わせて3程度、4未満には収まっている（実際にはもっと誤差は小さい）。ということで、その小さいかもしれない商に1000000007を掛けてA*Bから引いたら、1000000007以上であるなら1000000007を引くという処理を4回やる（今気づいたけど誤差は整数なので4未満なら3以下なんだから3回でよかった）。これでAC。実装上は、デバッグできるよう出力と同時に計算も実行し、出力はせずにランダムテストを回すこともできるようにした。
最初は簡単だと思ってたけど、解説を見たうえで1日くらいかかってるので、コンテスト中に通すのはやっぱりバケモン。
