桁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}\]