公式解説の漸化式を見ると、FFT により高速化できることが分かります。

\(\text{dp}[2^{n+1}-1]\) までの値がすべて \(\text{dp}[2^{n}-1]\) までの値から計算されているところに注意しましょう。具体的には以下の通りです。

\(C[i] := \binom{N}{2i}\) とおきます。

• \(\text{dp}[0], \ldots, \text{dp}[2^n-1]\) が計算できているとする
• \(\text{dp}[0], \ldots, \text{dp}[2^{n+1}-1]\) が次の式に従って計算できる
  • \(\text{dp}[2m] = \sum_{i+j=m}\text{dp}[i]C[j]\)

計算量 \(O(M\log M)\) 解法になりました。

解答例：https://atcoder.jp/contests/arc116/submissions/21369345

計算量解析

FFT を \(O(\log M)\) 回程度行うため、\(O(M\log^2M)\) との勘違いが起こりやすいですが。

長さ \(\frac{M}{2^n}\) のFFT を行う形になるため、

\(\sum_{n=0}^{\infty} \frac{M}{2^n}\log \frac{M}{2^n}\leq \sum_{n=0}^{\infty}\frac{M}{2^n}\log M\leq 2M\log M\)

などの計算から、全体で \(O(M\log M)\) 時間であることが分かります。

二項係数も \(M\) 番目までしか要らないので、前計算は \(O(M)\) 時間で行うことができます。