この解法は主として yuto1115 さんによるものです。

\(\mathrm{mu}_n, \mathrm{se}_n, \mathrm{ar}_n\) をそれぞれ以下のように定める。

• 「\(M\) 以下の非負整数からなる大きさ \(n\) の multiset で、総 xor が \(X\)」の個数を \(\mathrm{mu}_n\) とする。
• 「\(M\) 以下の非負整数からなる大きさ \(n\) の set で、総 xor が \(X\)」の個数を \(\mathrm{se}_n\) とする。
• 「\(M\) 以下の非負整数からなる長さ \(n\) の array で、総 xor が \(X\)」の個数を \(\mathrm{ar}_n\) とする。

求めるものは \(\mathrm{mu}_N\) である。以下、単に multiset, set, array と書いた場合、\(M\) 以下の非負整数からなり、総 xor が \(X\) であるようなもののみを指す。多重集合、集合、数列と書いた場合はそのような制限を課さないものとする。

set と array の対応

array を set にうつす写像として「array を、その要素のうち奇数回登場するもののなす set に送る写像」 を \(f\) とする。例えば、\(f((1,6,2,2,3,2,3)) = \{1,2,6\}\) である。
大きさ \(m\) の set \(S\) を固定したとき、\(f(A)=S\) となる長さ \(n\) の array \(A\) の個数を考える。これは「各要素が \(M+1\) 種類のいずれかで、そのうち指定された \(m\) 個の要素のみがちょうど奇数回現れる長さ \(n\) の array」の個数に等しい。この値を \(c_{n,m}\) と置くと、\(\mathrm{ar}_n=\sum_{m=0}^{n}c_{n,m}\mathrm{se}_m\) が成り立つことがわかる。

set と multiset の対応

多重集合を集合へうつす自然な写像「多重集合を、その各要素のなす集合に送る写像」を \(g\) とする。例えば \(g(\{\!\!\{1,1,2,4,4,4\}\!\!\})=\{1,2,4\}\) である。
大きさ \(m\) の set \(S\) を固定したとき、\(g(T)=S\) となる大きさ \(n\) の multiset \(T\) の個数を考える。これは「全ての要素が偶数であり、総和が \(n-m\) である長さ \(M+1\) の数列」の個数と等しい（そのような数列を 0-indexed で \(A\) としたとき、\(S\) に \(i\) を \(A_i\) 個追加した multiset を対応させる）。この数列の個数は \((n-m)/2\) が整数のとき \(\binom{(n-m)/2+M}{(n-m)/2}\) であり、そうでないとき \(0\) である。よって、\(\mathrm{mu}_n=\sum_{k=0}^{n/2} \binom{k+M}{k} \mathrm{se}_{n-2k}\) が成り立つことがわかる。

\(\mathrm{mu}_N\) の計算

• \(c_{*,*}\) は、数列の先頭の要素が指定された \(m\) 種類のいずれかであるか場合分けすることで、漸化式 \(c_{n,m}=m c_{n-1,m-1}+(M+1-m)c_{n-1,m+1}\) が成り立つことがわかる。したがって、\(n,m\leq N\) の範囲の \(c_{n,m}\) 全てを \(O(N^2)\) で求めることができる。
• \(\mathrm{ar}_n\) は桁 DP により \(O(n^2\log M)\) で求めることができる。したがって、\(n\leq N\) の範囲の \(\mathrm{ar}_n\) 全てを \(O(N^3\log M)\) で求めることができる。
• \(\mathrm{se}_n\) は \(\mathrm{ar},c\) が必要なだけ求まっているとき、 \(O(n)\) で求めることができる。したがって、\(n\leq N\) の範囲の \(\mathrm{se}_n\) 全てを \(O(N^2)\) で求めることができる。
  • \(c_{n,n}\) による除算を行うが、この値は定義より \(n!\) に等しいため、制約の範囲でゼロ除算は起こらない。
• \(\mathrm{mu}_N\) は \(\mathrm{se}\) が必要なだけ求まっているとき、 \(O(N)\) で求めることができる。

以上より、\(O(N^3\log M)\) でこの問題が解けた。

なお \(n\leq N\) の範囲の \(\mathrm{ar}_n\) 全てを求めるのは \(O(N \log M)\) でできるため、全体で \(O(N^2 +N\ \log M)\) でこの問題を解くことも可能である。