公式解説の焼き直しです。

定義

• 数列 \(a\) に対し、その \(k\) 番目の要素を \(a_k\) と表す。
• \(i\) 番目の要素が \(1\) であり、それ以外の要素が \(0\) である数列を \(e^i\) と表す。
• 長さの等しい 2 つの数列 \(a,b\) に対し、それらと長さの等しい数列 \(a+b\) を \((a+b)_k=a_k+b_k\) と定める。
• 数列 \(a\) と整数 \(m\) に対し、\(a\) と長さの等しい数列 \(ma\) を \((ma)_k=ma_k\) と定める。
• 長さの等しい 2 つの数列 \(a,b\) に対し、それらと長さの等しい数列 \(a\odot b\) を \((a\odot b)_k=a_kb_k\) と定める。
• 長さ \(2^L\) の2 つの数列 \(a,b\) に対し、長さ \(2^L\) の数列 \(a\otimes b\) を \((a\otimes b)_k=\sum_{i\oplus j=k}a_i b_j\) と定める。（これをXOR畳み込みという）
• 長さ 2 ベキ の数列 \(a\) に対し、\(a\) をアダマール変換した数列を \(H(a)\) と表す。
• 多項式 \(f\) に対し、その \(k\) 次の係数を \([x^k]f\) と表す。
• 多項式列 \(a\) に対し、その \(k\) 次の係数からなる数列を \([x^k]a\) と表す。

性質

• \(H(a\otimes b)=H(a)\odot H(b)\)
• \(H(a+ b)=H(a) +H(b)\)（線形性）
• \(H([x^m]a)=[x^m]H(a)\)（線形性から明らか）
• 長さ \(2^L\) の数列 \(a\) に対し、\(H(H(a))=2^L a\)

前提知識

この問題のいくつかの点を変更した次の問題をまず考える。
「数列に対して、その要素の総積をスコアとします。長さ \(N\) の数列の部分列であって、長さが \(M\) の倍数であるもののスコアの総和を求めてください」
この問題の答えは \(\sum_k[x^{kM}]\prod_i(1+A_ix)\) である。 もとの問題を解く際にも同様のアイディアを使う。

もとの問題の解法

スコア の定義を変更し、\(K\) 乗する前のものとする。求めるものはスコアの \(K\) 乗和となる。

各 \(s=0,\ldots,2^{20}-1\) に対し、スコアが \(s\) であるような部分列の個数がわかれば十分。空列のスコアは \(0\) となることから、空列も含めた \(2^N\) 個の部分列を考えて良い。

まず \(M=1\) の場合を考える。

各 \(i=1,\ldots,N\) に対し、長さ \(2^{20}\) の数列 \(a^i\) を \(a^i=e^0+e^{A_i}\) と定める。このとき、スコアが \(k\) であるような部分列の個数は \((\bigotimes_{i=1}^{N}a^i)_k\) となる。これをアダマール変換した数列は \(H(\bigotimes_{i=1}^{N}a^i)=\bigodot_{i=1}^NH(a^i)\) となる。右辺を考える。

\(H(a^i)=H(e^0)+H(e^{A_i})\) であり、任意の \(k\) で \(H(e^0)_k=1\)、\(|H(e^x)_k|=1\) であることから、\(H(a^i)_k\) の値は \(H(e^{A_i})_k\) が \(1\) か \(-1\) かによって \(2\) か \(0\) である。よって、\((\bigodot_{i=1}^NH(a^i))_k\) を求めるには、\(H(e^{A_i})_k=1\) となる \(i\) の個数がわかれば良い。

ところで、\(H(\sum_i e^{A_i})=\sum_i H(e^{A_i})\) であることから、アダマール変換1回で、\(\sum_i H(e^{A_i})\) を求めることができ、各 \(k\) について、\(H(e^{A_i})_k=1\) となる \(i\) の個数が求まる。（なぜなら、\(H(e^{A_i})_k=1\) となる \(i\) の個数を \(b_k\)とすると、\(\sum_i H(e^{A_i})_k=1\times b_k+(-1)\times(N-b_k)\) なので）

以上で \(\bigodot_{i=1}^NH(a^i)\) が求まったので、\(\bigotimes_{i=1}^{N}a^i=\frac{1}{2^{20}}H(H(\bigotimes_{i=1}^{N}a^i))=\frac{1}{2^{20}}H(\bigodot_{i=1}^NH(a^i))\) により答えが求まる。

一般の \(M\) の場合を考える。

先ほどと同様に長さ \(2^{20}\) の多項式列 \(a^i\) を \(a^i=e^0+xe^{A_i}\) と定める。このとき、スコアが \(k\) で長さが \(m\) であるような部分列の個数は \([x^m](\bigotimes_{i=1}^{N}a^i)_k\) となるので、\(\sum_d[x^{dM}]\bigotimes_{i=1}^{N}a^i\) が求まればよい。

\(M=1\) の場合と同様の考察により、各 \(k\) について、ある具体的な \(b_k\) により\(H(\bigotimes_{i=1}^{N}a^i)_k=(1+x)^{b_k}(1-x)^{N-b_k}\) と書けることがわかる。全ての \(k\) について \(\sum_d[x^{dM}]((1+x)^{b_k}(1-x)^{N-b_k})\) が求まっていれば、これを \(c_k\) として、\(\sum_d[x^{dM}]\bigotimes_{i=1}^{N}a^i=\frac{1}{2^{20}}H(\sum_d[x^{dM}]H(\bigotimes_{i=1}^{N}a^i))=\frac{1}{2^{20}}H(c)\) により答えが求まる。

\(\sum_d[x^{dM}]((1+x)^i(1-x)^{N-i})=[x^0]((1+x)^i(1-x)^{N-i}\bmod (1-x^M))\) であることを用いると、\((1+x)^n,(1-x)^n \bmod (1-x^M)\) を全ての \(n\) について愚直に計算することで、 \(O(NM)\) で求めることができる。