\(0\) 以上 \(2^M-1\) 以下の整数からなる数列の基底 \((S_1,S_2,\dots,S_K)\) のうち、以下を満たすものを標準的な基底ということとします。

• \(0 < S_1 < S_2 < \dots < S_K < 2^M\) である。
• \(1 \le i < j \le K\) を満たす整数の組 \((i,j)\) に対し、\(S_i\) の top bit は \(S_j\) では立っていない。

非負整数列 \(0 \le X_1 < X_2 < \dots < X_K < M\) に対して、以下の値の総積の総和が求められれば良いです。

• \(A\) のうち、\(A\) の標準的な基底が \(K\) 個のベクトルからなり、かつ \(i\) 番目に小さい基底の top bit が \(2^{X_i}\) であるようなものの個数
• 上記のような基底を持つものに対する Xor Optimization Problem の解の期待値
• 非負整数列 \(1 \le Y_1 < Y_2 < \dots < Y_K < 2^M\) のうち、「\(1 \le i < j \le K\) に対して、\(Y_i\) の最上位 bit は \(Y_j\) では立っていない」かつ「\(1 \le i \le K\) に対して、\(Y_i\) の最上位 bit が \(2^{X_i}\)」を満たすものの個数

\(A\) のうち、\(A\) の標準的な基底が \(K\) 個のベクトルからなり、かつ \(i\) 番目に小さい基底の top bit が \(2^{X_i}\) であるようなものの個数を求めます。 基底が \({2^0,2^1,2^2,\dots,2^{K-1}}\) となるようなものの個数を求められれば良いです。

初め、\(S=\{ \}\) から初めて以下の操作を片方選んで行うことを \(N\) 回繰り返します。

• \(S\) の要素をいくつか選び、その \(\mathrm{XOR}\) によって作ることのできる非負整数 \(2^{|S|}\) 個のうちいずれかを選び \(A\) の末尾に追加する。
• \(0 \le i < 2^K\) かつ \(S\) の要素をいくつか選び、その \(\mathrm{XOR}\) によって作ることのできない整数 \(i\) を選び、\(A,S\) の末尾にそれぞれ追加する。このような \(i\) は \(2^K-2^{|S|}\) 個ある。

ただし、\(2\) 個目の操作は \(N\) 回のうち \(K\) 回ちょうど行う必要があります。

このようにして作れる \(A\) の個数は、\([x^{N-K}]\prod_{i=0}^{K} \frac{1}{1-2^ix} \times \prod_{i=0}^{K-1} (2^K-2^i)\) 個あります。ここで、\(f_K(x) = \prod_{i=0}^{K} \frac{1}{1-2^ix}\) と置きます。

\((1-x)f_K(x) = (1-2^{K+1}x)f_K(2x)\) であるため両辺の \(x^{i+1}\) の係数に注目すると、\([x^{i+1}] f_K(x) - [x^i] f_K(x) = [x^{i+1}] 2^{i+1}f_K(x) - [x^i]2^{K+i+1} f_K(x)\) より、\([x^{i+1}](1-2^{i+1}) f_K(x) = [x^i](1-2^{K+i+1})f_K(x)\) を得ます。

より、\(\displaystyle [x^i]f_K(x) = \prod_{j=1}^{K} \frac{1-2^{i+j}}{1-2^j}\) となります。よって、\(1 \le K \le M\) に対し、\([x^{N-K}]f_K(x)\) を \(\mathrm{O}(N\log N)\) で列挙することができます。以降、この個数を \(B_K\) と置きます。

上記のような基底を持つものに対する Xor Optimization Problem の解の期待値を求めます。

これは \(X_i\) bit 目は必ず立っていることに注意すると \(\displaystyle \frac{(2^{X_M+1}-1) + (\sum_{i=1}^{K} 2^{X_i})}{2}\)となります。

非負整数列 \(1 \le Y_1 < Y_2 < \dots < Y_K < 2^M\) のうち、「\(1 \le i < j \le K\) に対して、\(Y_i\) の最上位 bit は \(Y_j\) では立っていない」かつ「\(1 \le i \le K\) に対して、\(Y_i\) の最上位 bit が \(2^{X_i}\)」を満たすものの個数を求めます。

これは \(Y_i\) については、\(X_i\) bit 目が最上位 bit であり、かつ \(1 \le j < i\) に対し \(X_j\) bit 目は立っていない必要があるため \(\displaystyle \prod_{i=1}^{K} 2^{X_i - (i-1)}\) 個あります。

よって、この問題は非負整数列 \(0 \le X_1 < X_2 < \dots < X_K < M\) に対して、以下の値の総和を求める問題となります。

・\(B_K \times \displaystyle \frac{(2^{X_K+1}-1) + (\sum_{i=1}^{K} 2^{X_i})}{2} \times \prod_{i=1}^{K} 2^{X_i - (i-1)}\)

まず、分数の部分の \(\sum_{i=1}^{K} 2^{X_i}\) 側を処理します。整理すると、\(B_K \times \sum_{i=1}^{K} 2^{X_i} \times 2^{-\frac{K(K-1)}{2}} \times \prod_{i=1}^{K} 2^{X_i}\) となります。\(K\) ごとに \(\sum_{i=1}^{K} 2^{X_i} \times \prod_{i=1}^{K} 2^{X_i}\) の総和を求めることを考えます。

\(2^0,2^1,\dots,2^{M-1}\) から \(K\) 個選び、その積を取ったものの総和を \(C_K\) と置きます。すると、\(K\) を固定した時の \(\sum_{i=1}^{K} 2^{X_i} \times \prod_{i=1}^{K} 2^{X_i}\) は \((2^M-1)C_K - (K+1)C_{K+1}\) となります。\(\sum_{i=1}^{K} 2^{X_i}\) を 「\(2^M-1-\) 余分なもの」と考えると上記の式が導出可能です。

次に、分数の部分の \(2^{X_K+1} - 1\) 側を処理します。整理すると \(\frac{B_K \times (2^{X_K+1} - 1) \times \prod_{i=1}^{K} 2^{X_i}}{2^{\frac{K(K-1)}{2}} }\) となります。\(2^{X_K+1} - 1\) の \(1\) は \(C_K\) を使い簡単に表せるため、以降 \(2^{X_K}\) について考えます。

\(K\) を固定した時、\(2^{X_K} \times \prod_{i=1}^{K} 2^{X_i}\) を求めればよいです。これは分割統治をすることで \(\mathrm{O}(M\log^2 M)\) で求めることができます。

よって本問題を \(\mathrm{O}(N\log N + M \log^2 M)\) で解くことができました。