■A - Coprime Pair
幅が大きい方から試すしかなさそう。
計算量が間に合うかどうかが問題。
問題の成約の下では、1500以上のサイズの素数砂漠は存在しないので間に合う。
■B - Count 1's
ここからここまでの区間をひっくり返すとどんだけ差分が出るかを考える。
区間の右を固定したときの、最大最小は累積和の考え方で簡単にわかる。
■C - Distinct Numbers
a[n-2]+2<=a[n-1]なら先手必勝になる。
これはa[n-1]をa[n-2]未満にした局面に手番のプレイヤーの必敗の局面が存在するなら、その局面を渡す
そうでない(手番のプレイヤーが必勝)ならa[n-1]をa[n-2]+1にして局面を渡せばいい。
a[n-2]+1=a[n-1]の場合を考える。
上記より操作後の最大と次に最大なものは差が１の状態を保つことが最善であり
最大のものは毎回１減るので答えがわかる(僕にはわからんかったけど)
■D - Prefix XORs
寄与の回数が二項係数になるのわかった。
二項係数の偶奇がリュカの定理より分かることもわかったけど
それ以上が進まず。
リュカの定理をライブラリに頼るのではなく、定義をちゃんと見直すと
Binomial(x+y,x)=1(mod2)となるのはxとyをそれぞれ2進数に直して同じ位置にbitが立っていたらNGとわかる。
これを読み替えると
十分大きな2べき(以下S)に対してS-1-xの立っているbitの位置がyの立っているbitの位置を包含していると同値になる
これは前回のARCでも使ったテクニック！
ということがわかれば、高速ゼータ変換の容量で求める事ができる。
