ABC267-Ex Odd Sum - ganmo::cout

巡回畳み込み解
問題:
状態が (選んだ要素の総和, 個数 mod 2) になってそのままでは2次元畳み込みが必要なように見えるが、巡回畳み込みを使えば1次元の畳み込みで解ける。
$\sum_i A_i \le 2^n$ を満たす最小の $n$ を選んで長さ $2^{n+1}$ の配列を用意し、各要素 $A_i$ を $A_i+2^n$ に読み替えてNTTをすると前半 $2^n$ 要素が偶数個選んだ状態に対応して、後半 $2^n$ 要素が奇数個選んだ状態に対応する。
制約が $\sum_i A_i \le 10^6$ なため最悪で $2^{\lceil \log_2 10^6 \rceil+1}=2,097,152$ 要素同士の畳み込みになるが、ACLなどを参考にして速い Cooley-Tukey FFT の実装を使うと間に合う。
実装例: