再帰的に解くことを考えます。問題は $u + 2s \leq N, u \ \& \ s = 0$ なる $\left( u, s \right)$ を数えるものになります。

$\left( u, s \right) = \left( 2k, 2l + 1 \right)$ となるものを数え上げることを考えるとこれは $k + 2l \leq \frac{N - 2}{2}, k \ \& \ l = 0$ なる $\left( k, l \right)$ を数えるものになります。
$\left( u, s \right) = \left( 2k, 2l \right)$ となるものを数え上げることを考えるとこれは $k + 2l \leq \frac{N}{2}, k \ \& \ l = 0$ なる $\left( k, l \right)$ を数えるものになります。
$\left( u, s \right) = \left( 2k + 1, 2l \right)$ となるものを数え上げることを考えるとこれは $k + 2l \leq \frac{N - 1}{2}, k \ \& \ l = 0$ なる $\left( k, l \right)$ を数えるものになります。

よって、答えをメモ化再帰で求めることができました。