あまり面白さはありませんが、別解を記録します。

要素数 \(n\) の非負整数の集合 \(S\) を考えます。 \(n = 0,1,2,\ldots ,N\) と \(d=0,1,2, \ldots ,30\) について、\(S\) の要素が \(\lfloor M/2^d \rfloor\) 以下としたとき、

• \(f(d,n)\) ： \(S\) の要素全体の XOR は \(\lfloor X/2^d \rfloor\) に一致する場合の数。
• \(g(d,n)\) ： \(S\) の要素全体の XOR は \(\lfloor X/2^d \rfloor\) XOR \(\lfloor M/2^d \rfloor\)に一致する場合の数。

問題の答えは \(n=0\) のときの結果から重複要素を改めて考慮することで求まります。この目標は kyopro_friendsさんによる解説 の set と同じです。

\(f(d+1,n)\) , \(g(d+1,n)\) から \(f(d,n)\) , \(g(d,n)\) を求めます。 \(n\) のときの \(S\) の要素は次の \(3\) 種類に分類できます。

• (1) \(\lfloor M/2^d \rfloor\) が偶数の場合、それ
• (2) 整数 \(x\) があって、 \(2x\) と \(2x+1\) が両方 \(S\) の要素となる場合、それら（ \(2x\) と \(2x+1\) のこと）
• (3) 上記以外

(3) の要素のみ考慮すると、 \(f(d+1,n)\) , \(g(d+1,n)\) で扱う集合の要素をすべて \(2\) 倍して、それらのうち新たに最下位ビットを \(1\) にする要素の個数の偶奇を場合分けすると処理できます。

(2) は、最下位ビットのみが XOR に寄与するのでそのような要素の個数を場合分けすることで処理できます。

(1) は、 \(f(d,n+1)\) , \(g(d,n+1)\) をクロスするように寄与します。

最下位ビットの寄与などはもっと具体的に計算すると、 \(d\) に関する繰り返しと \(n\) に関する繰り返し、 (2) の要素の個数で場合分け、最下位ビットの場合分けで十分なので、全体の計算量のオーダーは \(O(N^2 \log (M))\) と表せます。

実装例