ARC092 D Two Sequences

atcoder.jp

所感

基礎 * 大量だけど解けないね、悲しみ

問題概要

長さNの非負整数列a, b が与えられる。
a, bからそれぞれx, y を一つずつ取り出す方法はN²通りあるが、そのx + y のXORを計算せよ。

取った方針

XORなので各桁を独立に計算したくなるが、足し算を各桁独立に行えず死亡

正しい方針

a + b の二進i桁目(0-indexed)を求めるには二進i桁目までの a + bを計算すればよい。(それはそう)
二進i桁目までのみ考える時、mod 2ⁱ+1 で考えてよい。(二進i桁で表せる数は2ⁱ+1 - 1までなので)
ここで、a, b 共にmod 2ⁱ+1 を取っておくと、a + bは高々4 * 2ⁱ である。
2ⁱ = T とおくと、4T未満でi桁目が1となるのは[T, 2T) と[3T, 4T)である。(2進i桁目は2ⁱ ごとに繰り上がることを考えるとそれはそう)
よって、aを固定すると条件を満たすbの個数は二分探索で求められる。

得られた知見

・XOR -> 各桁独立に考える
・a + bのi桁目 は aのi桁目まで + b のi桁目まで と等しい
・n進i桁目(0-indexed) はnⁱごとに1増える(n = 10なら小学生でも知っている事実)
・n進i桁目までのみを考える時、mod nⁱ+1 で考える、n = 10で（ｒｙ
・modを取ると上限が定まり全探索ができることがある

解くのに必要な要素

・同上

周辺調査によって得られた知見

特になし