ARC #066 D
桁DPを使う.
\(a \oplus b \leq a + b\) であるので, \(v \leq N\) だけ考えればいい.
\(C(i, j)\) を \(i\) 桁目まで見た時に \(v = j\) となる組み合わせの数とする. このとき, \(a, b\) の \(i\) ビット目の組み合わせは以下の通りとなる.
- 両方 \(0\)
- 片方 \(1\)
- 両方 \(1\)
なお, 片方 \(1\) は \(a, b\) の \(i\) ビット目が \(0, 1\) の場合と \(1, 0\) の場合があるが, ともに \(u, v\) は同じ値になりダブルカウントしてしまうので, 片方しか考えなくていい.
しかし, このままでは \(v\) が大きくなるので解けない.
そこで, \(C(i, j)\) を \(i\) 桁目まで見たときに \(N\) の上位 \(i\) ビットと \(v\) の上位 \(i\) ビットの差が \(j\) である組み合わせの数とする. \(j \geq 2\) の場合は遷移後でも \(j \geq 2\) である (下遷移表参照) ので, これで解くことができる.
遷移表は以下の通りである.
\(N\) の \(i\) ビット目が \(0\) の場合:
j/a,b | 両方0 | 片方1 | 両方1 |
---|---|---|---|
0 | 0 | over | over |
1 | 2- | 1 | 0 |
2- | 2- | 2- | 2- |
\(N\) の \(i\) ビット目が \(1\) の場合:
j/a,b | 両方0 | 片方1 | 両方1 |
---|---|---|---|
0 | 1 | 0 | over |
1 | 2- | 2- | 1 |
2- | 2- | 2- | 2- |
よって, 漸化式は以下のようになる.
\(N\) の \(i\) ビット目が \(0\) の場合:
\[\begin{align} C(i+1, 0) &= C(i, 0) + C(i, 1) \\ C(i+1, 1) &= C(i, 1) \\ C(i+1, 2) &= C(i, 1) + 3C(i, 2) \end{align}\]\(N\) の \(i\) ビット目が \(1\) の場合:
\[\begin{align} C(i+1, 0) &= C(i, 0) \\ C(i+1, 1) &= C(i, 0) + C(i, 1) \\ C(i+1, 2) &= 2C(i, 1) + 3C(i, 2) \end{align}\]