愚直な動的計画法を行うと、計算量が \(\mathrm{O}(NM)\) となってしまい実行制限時間に間に合いません。

ここで、「\([x^ny^m]f(x,y):=\) \(A\) から要素を \(n\) 個選び総和を \(m\) にする方法の個数」という母関数 \(f\) を考えます。\(f=\prod_{i=1}^{N} (1 + xy^{A_i})\) が成り立ちます。

今求めたい値は、\(\sum_{i=0}^{\infty} [x^{2i+1}y^M] f(x,y)\) です。

ところで、多項式 \(g(x)\) に対して \(g(1)\) と \(g(-1)\) を考えます。これらは \(a_i = [x^i] g(x)\) としたとき、\(g(1)=\sum_{i=0}^{\infty} a_i,g(-1)=\sum_{i=0}^{\infty} (-1)^i \times a_i\) です。

よって、\(g(1)-g(-1)=\sum_{i=0}^{\infty} 2 \times a_{2i+1}\) となります。

なので、\(\sum_{i=0}^{\infty} a_{2i+1} = \frac{g(1)-g(-1)}{2}\) です。

元の問題に戻ります。上記を使うと、求めたい値 \(\sum_{i=0}^{\infty} [x^{2i+1}y^M] f(x,y)\) は \([y^M] \frac{f(1,y)- f(-1,y)}{2}\) と等しいです。よって、\(\prod_{i=1}^{N} (1+y^{A_i})\) と \(\prod_{i=1}^{N} (1-y^{A_i})\) を計算し、\([y^M]\) の係数の差を求めることによってこの問題を解くことができます。

愚直に畳み込みを使っていては間に合いませんが、以下のアルゴリズムを使うことによって計算量を早くすることができます。

• 多項式の列 $f_1,f_2,\dots,f_X$ がある。$\prod_{i=1}^{X} f_i$ を求めることを目標とする。
• 列の長さが $1$ になるまで以下の操作を繰り返す。
• 列の末尾に $f_1 \times f_2$ を加え、列から $f_1,f_2$ を削除する。
• $f$ の長さが $1$ となったとき、$f_1$ が求めたかった多項式である。

計算量解析は、\(f_1,f_2,\dots,f_N\) は \(\mathrm{O}(\log X)\) 回しか畳み込みに使われないことより \(\mathrm{O}(Y\log Y\log X)\) です。ここで、\(Y=\sum_{i=1}^{X} \deg f_i\) です。

元の問題だと、\(X=N,Y=M\) より計算量は \(\mathrm{O}(M\log N \log M)\) です。この計算量は十分高速です。

また、以下の式変形を行うことによって更に高速化することが可能です。

\(\begin{aligned} \displaystyle \prod_{i=1}^{N} (1 - x^{A_i}) &= \exp\left(\sum_{i=1}^{N} \log(1-x^{A_i})\right) \\ &= \exp\left(\sum_{i=1}^{N} \sum_{j=1}^{\infty} \frac{x^{jA_i}}{j}\right) \end{aligned}\)

ここで、\(A_i\) が同じ値ごとに \(\sum_{j=1}^{\infty} \frac{x^{jA_i}}{j}\) を \(M\) 次まで求めることにより、\(\mathrm{O}(M\log \max A)\) で \(\sum_{i=1}^{N} \sum_{j=1}^{\infty} \frac{x^{jA_i}}{j}\) を求めることができます。その後、\(O(M\log M)\) で \(\exp\) を取ることにより、\((1-x^{A_i})\) の積を \(\mathrm{O}(N+M(\log M + \log \max A))\) で求めることができます。