AtCoder Regular Contest 066 D - Xor Sum - アルゴリズム忘備録

今更書くまでもない超有名問題だけどかなり手こずったのでメモ。基本的に $xor$ 系は和ととても相性が悪い。

問題の性質を考えると、 $a \oplus b = u, a + b = v$ を満たすとき、常に $u \le v$ であるため、 $v \le N$ だけ考えればよい。また、足し算の有名な言い換え $a + b = a \oplus b + a \ and \ b * 2$ があります。これはつまり、 $a$ と $b$ のbitごとの交換に関して不変です。つまり、 $a$ と $b$ の各bitは $(0, 0), (0, 1), (1, 1)$ の3通りだけ考えれば良いです。

$dp[i][s]$ を上からi ビット目まで見たときに、 $s * 2^i$ だけ $N$ より小さい場合の組み合わせ数と定義します。このとき、 $s$ が2以上の場合は、i+1ビット目について、 $s * 2^{i+1} \ge 4*2^i$ となるため、例え今見ているビットが $(1,1)$ で、 $N$ のビットが $0$ だったとしても $2*2^i$ 以上 $N$ より小さいことは確定します。そのため、 $s$ は状態として $0,1,2$ の3通りだけ見るdpを考えればよいです。