\(f_N(M)\) を，長さ \(N\) の数列 \(A\) で，すべての \(i=1,2,\dots,N\) について \(A_i + (A_{i-1} \& A_{i+1})=M\) を満たすものの個数とします．

\(M=0\) のとき

条件を満たす \(A\) は \((0,0,\dots,0)\) のみなので， \(f_N(0)=1\) です．

\(M=1\) のとき

数列 \(A\) が条件を満たす必要十分条件は，「\(A\) において \(0\) が \(2\) つ以上連続せず，かつ， \(1\) が \(3\) つ以上連続しない」です．この条件を満たす \(A\) の個数は，以下のグラフにおいて，ある頂点から \(N\) 本の辺を通って同じ頂点に戻ってくるような経路の数と等しいです．これは，行列累乗によって \(O(\log N)\) 時間で計算できます．

\(M\) が \(2\) 以上の偶数のとき

\(A_i\) はすべて偶数またはすべて奇数です． \(A\) に奇数が存在すれば，その両隣もまた奇数である必要があるからです．

\(A_i\) がすべて偶数であるような \(A\) の個数は \(f_N(M/2)\) に等しいです．

\(A_i\) がすべて奇数であるような \(A\) の個数は \(f_N(M/2-1)\) に等しいです．

よって， \(f_N(M)=f_N(M/2)+f_N(M/2-1)\) です．

\(M\) が \(3\) 以上の奇数のとき

\(A\) において奇数が \(3\) つ連続することはありません．よって， \(A_i + (A_{i-1} \& A_{i+1})\) の最下位 bit では繰り上がりは発生しません．この性質により， \(A\) の最下位 bit とそれより上の bit を独立に選ぶことができます． \(f_N(M)=f_N(1) \times f_N((M-1)/2)\) です．

以上をメモ化再帰で実装することで， \(f_N(M)\) の値を \(O(\log N + \log M)\) 時間で計算できます．