下記の \(2\) つの条件をともに満たす長さ \(L\) の数列 \(A\) を、長さ \(L\) の良い数列と呼びます。

• すべての \(i = 1, 2, \ldots, L\) について、\(0 \leq A_i \leq M\)
• \(A_1 \oplus A_2 \oplus \cdots \oplus A_L = X\)

問題文中の条件とは異なることに注意してください。

[1] 良い数列の個数を求める

長さ \(L\) の良い数列の個数 \(f(L)\) をすべての \(L = 0, 1, 2, \ldots, N\) について求めます。 \(L\) を一つ固定して \(f(L)\) を動的計画法（いわゆる桁 DP ）で求めます。 良い数列 \(A\) の全 \(L\) 要素の値を上位ビットから順に確定させていくことを考え、

\(\mathrm{dp}[i][j] = \) （全 \(L\) 要素の上位 \(i\) ビット目までを決定する方法のうち、「その時点で \(M\) より真に小さいことが確定した要素」の個数が \(j\) であるものの個数）

というテーブルを埋めます。 \((i+1)\) ビット目を決定する際、「 \(M\) より真に小さいことがまだ確定していない \((L-j)\) 個の要素のうち何個の要素を \(1\) にするか」に対応した \((L-j+1)\) 本の遷移を \(\mathrm{dp}[i][j]\) から行います。

各 \(L\) についてこの DP の時間計算量は \(O(L^2\log \max\lbrace M, X\rbrace)\) であり、すべての \(L\) について計算すると \(O(N^3\log \max\lbrace M, X\rbrace)\) 時間です。

[2] 重複のない良い数列の個数を求める

要素の重複がない良い数列の個数 \(g(L)\) をすべての \(L = 0, 1, 2, \ldots, N\) について求めます。 \(L\) を一つ固定し、\(g(L)\) の値を \(f(L)\) から「要素の重複がある長さ \(L\) の良い数列の個数」を引くことで求めます。

\(A\) に奇数個含まれる整数を奇妙な整数と呼ぶことにし、 奇妙な整数である \(A\) の要素を奇妙な要素と呼ぶことにします。

数列 \(A\) の総 XOR は \(A\) の奇妙な整数の総 XOR であることに注意すると、要素の重複がある長さ \(L\) の良い数列であって、

• 奇妙な要素の個数が \(i\) 、
• 奇妙な整数の個数が \(j\) 、
• \(A\) に含まれる奇妙でない整数の個数が \(k\)

であるものは以下の方法で得られます。

• まず、全 \(L\) 要素のうち奇妙な要素の位置 \(i\) 個を選ぶ（全 \(\binom{L}{i}\) 通り）。
• \(i\) 個の奇妙な要素を、サイズが奇数である \(j\) 個のグループに分け（ \(\mathrm{odd}(i, j)\) 通りとおく）、\(j\) 個のグループそれぞれに総 XOR が \(X\) であるような相異なる整数を割り当てる（ \(g(j)\) 通り）。
• \((L-i)\) 個の奇妙でない要素を、サイズが偶数である \(k\) 個のグループに分け（ \(\mathrm{even}(L-i, k)\) 通りとおく）、\(k\) 個のグループそれぞれに、\(0\) 以上 \(M\)以下の整数からすでに割り当てた \(j\) 個を除いた \((M+1-j)\) 個の整数のうちから相異なる整数を割り当てる（\(\prod_{l = M+1-j-k+1}^{M+1-j} l\) 通り）。

よって、その個数は

\[\binom{L}{i} \mathrm{odd}(i, j) g(j) \mathrm{even}(L-i, k) \prod_{l = M+1-j-k+1}^{M+1-j} l\]

です。したがって、要素の重複がない良い数列全体の個数は

\[\sum_{i = 0}^L \binom{L}{i} \sum_{j = 0}^{\min\lbrace L-1, i\rbrace} \mathrm{odd}(i, j) g(j) h(L-i, j)\]

と求まります。ここで、

\[h(x, y) \coloneqq \sum_{k= 0}^{x} \mathrm{even}(x, k) \prod_{l = M+1-y-k+1}^{M+1-y} l\]

です。\(h(\cdot, \cdot)\) の必要な値はまとめて \(O(N^2)\) 時間で前計算できます。 また、\(\mathrm{odd}(\cdot, \cdot), \mathrm{even}(\cdot, \cdot)\) はそれぞれ、

\[\mathrm{odd}(i, j) = \sum_{k:\text{奇数}} \binom{i-1}{k-1} \mathrm{odd}(i-k, j-1)\]

および

\[\mathrm{even}(i, j) = \sum_{k:\text{偶数}} \binom{i-1}{k-1} \mathrm{even}(i-k, j-1)\]

によって \(O(N^2)\) 時間で前計算できます。

よって、各 \(L\) について \(O(N^2)\) 時間で \(g(L)\) を求めることができます

[3] 本問題の答えを求める

問題文中の条件を満たす数列は、長さ \(N\) 以下の狭義単調増加な良い数列に、\(0\) 以上 \(M\) 以下の整数をそれぞれ偶数個ずつ追加して得られる長さ \(N\) の数列です。 追加する整数の総数を \(2i\) 個に固定した場合の、問題文中の条件を満たす数列の個数は、

• 長さ \((N-2i)\) の狭義単調増加な良い数列の個数 \(g(N-2i)/(N-2i)!\) と、
• \(0\) 以上 \(M\) 以下の整数を、それぞれ偶数個ずつ、合計 \(2i\) 個追加する方法の個数 \(\binom{M+i}{i}\)

の積であるため、本問題の答えは

\[\sum_{i = 0}^{\lfloor \frac{N}{2} \rfloor} \frac{g(N-2i)}{(N-2i)!}\binom{M+i}{i}\]

となります。