コンテストページ
yukicoder contest 236
✔A - Add
AB 以下のチェックリストを作って、x ≦ B, y ≦ A を全探索です。
✔B - Convolution
GCD は ( a, b ) -> ( a, a+b ) で不変ですから、この性質をふんだんに使いましょう。
まず、i & j=k とありますが、これは i & j ⊇ k に書き換えてよいです。 すると因数分解ができます。各 i に対してそれを包含する添字全体に渡る和を書いたような数列の GCD を計算して 2 乗をすればよいです。
さらに、この和も先程のように掃き出し法をすると、単に a の GCD を計算すれば良いことがわかります。−1 は 0 にしておきましょう。
✔C - Inversion
N が P の平方剰余であることが、偶置換である条件であることをエスパーしました。（はい！？）
ここからは手慣れた手付きです。平方剰余の相互法則でググり、Wikipedia に書いてある定理を写しました。
✖D - Hadamard
わかりませんでした。
✖ E - Present
移動できる場所の個数は 2 の N 乗です。
移動できる場所の個数を最大化するような S の個数は、M 次元空間の線形独立な N 個のベクトルの組の個数を N の階乗で割ったものです。
移動できる場所の個数を最大化するときの、移動できる場所の集合の個数は、M 次元空間の N 次元線形空間の個数です。
どれも、一般線形群の元の個数を計算する感じで計算すれば、Θ(N) で計算することが出来ます。
自叙伝
ところで私は「 N ≦ M なら簡単なのに……」と頭をひねっていました。それの assert を入れて通るかどうか、試そうかとも思ったのですが、ギリギリまで粘りました。終了 15 分前、諦めてそれだけ提出しようと書き始めたときです。気づいてしまったんですよね。
制約は N ≦ M です。
これなら（☆ 4 にしては）簡単じゃないんですか！！
一般線形群に慣れているからそう感じるだけかもしれませんが、そのあたりメタ読みが狂いがちですから、気をつけたいところです。
