公式解説を見ればわかるのですが、これは以下の問題と同値です。

以下の条件を満たす非負整数列 \(B=(B_{1},B_{2},...,B_{2N-K+1})\) の場合の数を求めてください。

• \(\sum B=\frac{M}{K}\)
• \(B_{i}<K(1\leq i\leq N-K+1)\)

これを包除原理でときます。

簡単バージョンが過去にABCで出題されています。(包除原理で解く解説)

\(1\leq i\leq N-K+1\) のうち制約を違反している個数が \(L\) 個のとき、その場合の数は \(\dbinom{\frac{M}{K}+2N-K-KL}{2N-K}\)、制約を違反している \(i\) の数の場合の数は \(\dbinom{N-K+1}{L}\) です。

ここまでわかれば \(0\leq L\leq N-K+1\) について以上の値の積を計算し、 \(L\) の偶奇で足すか引くかを決めることで求まります。