基本的な方針は公式解説と同じですが、必要十分条件による問題の言い換え後の数え上げ部分を形式的冪級数の言葉を用いずに解説します。

全体の個数

包除原理を適用します。総和が \(K\) 以下の偶数であって、\(X_1, X_2, \ldots , X_i\) が \(M\) より大きくなる非負整数列 \(X\) の個数を \(f(i)\) とすると、求めるものは \(\displaystyle\sum_{i=0}^{N} \binom{N}{i}(-1)^if(i)\) です。
以下、各 \(i\) に対して \(f(i)\) を求めます。
数列の総和が \(S\) となるものは \({}_N \mathrm{H}_{S-(M+1)i}\) 個あるので、各 \(S\) に対して足し合わせることで \(f(i)\) は適切な整数 \(t\) により\(\displaystyle\sum_{j=0}^{t}{}_N \mathrm{H}_{2j}\) あるいは \(\displaystyle\sum_{j=0}^{t}{}_N \mathrm{H}_{2j + 1}\) の形で表されます。したがって \({}_N \mathrm{H}_j\) を \(1\) つ飛ばしに累積和を取ったものを前計算しておけばよいです。

違反箇所を二つ固定したときの数列の個数の総和

\(i = 1,2\) で違反している数列の個数を数え上げます。
\(X_2\) と \(Y \coloneqq \displaystyle\sum_{i=4}^{N} X_i\) について全探索します。

• \(|X_1 - X_3| < X_2 - Y\)
  
• \(X_1 + X_3 \leq K - X_2 - Y\)
• \(X_1 + X_3 \equiv X_2 + Y \pmod 2\)

を満たす \((X_1,X_3)\) の組の個数がわかればよいです。これは、\(A_{|i-j|,i+j}\) に \(1\) を加算した配列の二次元累積和を取ったものを \(i+j\) が偶数になるものと奇数になるものそれぞれについて前計算しておくことで \(\mathrm{O}(1)\) で求められます。