No.050 D

桁DPを使う.

まず, $u \leq v$ となるので, $v = a + b \leq N$ だけ考えればいい.

$a, b$ ともに $i$ 桁目まで見たときに $a + b = j$ となる組み合わせの数を $D(i, j)$ とする.

このとき, $i$ 桁目における $a, b$ の組み合わせパターンは両方が $0$ か片方が $1$ か両方が $1$ かの3パターンである. 片方が $1$ のパターンはどちらが $1$ かは気にしなくてもいい. (というか気にしてしまうと $u, v$ をダブルカウントしてしまう. $a \oplus b$, $a + b$ ともにどちらが $1$ でも同じ値になるので片方だけカウントしなければならない)

しかし, この桁DPを使うと $j$ が最大 $N$ となるので, $O(N\log N)$ の計算量となってしまう.

そこで, $D(i, j)$ を上位 $i$ 桁目まで見たときに $N$ の上位 $i$ ビットと $a+b$ の上位 $i$ ビットの差が $j$ になる組み合わせの数とする. こうすると $j \geq 2$ の場合はその次の桁でどうがんばっても $j \geq 2$ からは脱出できないので, $j = 2$ にまとめてしまっていい. (後述の表を見るとわかるかも)

上位 $i-1$ ビットの $N$ と $a+b$ の差と $i$ ビット目の $a, b$ の組み合わせパターンで上位 $i$ ビットの $N$ と $a+b$ の差を表にすると下のようになる.

$N$ の上から $i$ ビット目が $0$ である:

	両方0	片方1	両方1
0	0	over	over
1	2	1	0
2	2	2	2

よって, このときのDPの更新は以下の通りである.

$$\begin{align} D(i+1, 0) &= D(i, 0) + D(i, 1) \\ D(i+1, 1) &= D(i, 1) \\ D(i+1, 2) &= D(i, 1) + 3D(i, 2) \end{align}$$

$N$ の上から $i$ ビット目が $1$ である:

	両方0	片方1	両方1
0	1	0	over
1	2	2	1
2	2	2	2

よって, このときのDPの更新は以下の通りである.

$$\begin{align} D(i+1, 0) &= D(i, 0) \\ D(i+1, 1) &= D(i, 0) + D(i, 1) \\ D(i+1, 2) &= 2D(i, 1) + 3D(i, 2) \end{align}$$

この桁DPなら計算量は $O(\log N)$ である.