[1] 頻度列による言い換え

\(0\leq x \leq 2 ^ M - 1\) に対して，\(A_i = x\) を満たす \(i\) の個数を

\[C[x]\]

と書くことにします．答えを \(\mathrm{ANS}\) と書くことにすれば，

\[ \begin{aligned} \mathrm{ANS}[0] &= \sum_i \lfloor C[i]/2\rfloor, \\ \mathrm{ANS}[X]& = \sum_{i<j, i\oplus j=X} \min(C[i],C[j])\quad (X\neq 0) \end{aligned} \]

となることはすぐに分かります．\(\mathrm{ANS}[0]\) は簡単に計算できるため，後者のタイプの計算を高速に行うことが課題です．

---

[2] 全列挙による計算

すべての \((i,j)\) を列挙して上の計算を行えば，\(O((2^M)^2)\) 時間で答を求められます．

また，\(C[i], C[j]>0\) であるような \((i,j)\) のみを列挙するようにすれば，\(O(N^2)\) 時間で答えを求められます．

---

[3] XOR 畳み込みを用いる方法

整数 \(a,b\) に対して

\[ [a\leq b]=\begin{cases}1 & (a\leq b) \\ 0 & (a > b)\end{cases} \]

と書くことにすると，

\[ \min(C[i],C[j]) = \sum_{x=1}^{\infty} [C[i]\geq x]\cdot [C[j]\geq x] \]

と式変形できます．

式変形に関する説明

ここでは「$\min(C[i],C[j])$ の得点を獲得します」というときに，これを

• $\min(C[i],C[j])\geq 1$ ならば $1$ 点を獲得する．
• $\min(C[i],C[j])\geq 2$ ならば $1$ 点を獲得する．
• $\min(C[i],C[j])\geq 3$ ならば $1$ 点を獲得する．
• $\cdots$

というように，獲得する得点を分解して考えています．

$\min(a,b)\geq x$ という条件は「$a\geq x$ かつ $b\geq x$」のように成分ごとの独立な条件に分解できるため，扱いやすいことが多いです．

したがって答を計算するには，\(x=1,2,\ldots,\max(C)\) について， \(S_i = [C[i]\geq x]\) により定まる列 \(S\) を考えて，\(S\) と \(S\) の XOR 畳み込みつまり

\[ T_k=\sum_{i\oplus j=k}S_iS_j \]

を求めればよいです（\(i < j\) の場合を取り出すにはこれを \(2\) で割ればよいです）．

この解法の計算量は \(O(M\cdot 2^M\cdot \max(C))\) 時間となります．

なお，異なる \(x\) から同じ列 \(S\) が定まることに注意して，\(\max(C)\) の部分を「\(C\) の種類数」とすることもできます（これは \(O(\sqrt{N})\) です）．

---

[4] 計算方法の使い分け

これら \(2\) 種の計算方法を使い分けます．適当なしきい値 \(K\) をとり，次のように計算します．

• \(x=1,2,\ldots,K\) について [3] の方法で計算する．
• この時点で正しく計算できていないのは，\(\min(C[i],C[j])> K\) となる場合の計算である．このような組 \((i,j)\) を全列挙し，そのような \((i,j)\)についての計算を修正する．

例えば \(K=10\) 程度ととることで，本問題の制約に対して十分高速に答を求めることができます．なお実装によりますが，\(2\leq K\leq 500\) 程度の幅広い \(K\) で正答が得られることを確認しています．

なお計算量オーダーは

\[ O(K\cdot M2^M + (N/K)^2) \]

であり，\(K = (N^2/M2^M)^{1/3}\) ととることで

\[ O((NM2^M)^{2/3}) \]

となります．