\(M \bmod K = 0\) でない場合は解は \(0\) です。以降 \(M = \frac{M}{K}\) とします。

\(A_i\) を \(K\) 減らす方を操作 \(1\)、\(A_i,A_{i+1},\dots,A_{i+K-1}\) を \(1\) ずつ減らす方を操作 \(2\) と呼びます。

ある \(i\) に操作 \(2\) を \(K\) 回適用させることは、\(i,i+1,\dots,i+K-1\) に操作 \(1\) を \(1\) 回ずつ適用させることと同じなのである \(i\) に対する操作 \(2\) の回数は \(K\) 回未満のみとしてよいです。以下、そう仮定します。

\(A_1 \bmod K\) は操作 \(1\) では減らないため、操作 \(2\) で \(0\) にする必要があります。よって、操作 \(2\) は \(i=1\) に対して \(A_1 \bmod K\) 回行うこととなります。同様の議論を \(A_2,A_3,\dots,A_{N-K+1}\) に対して行うことで \(i=2,3,\dots,N-K+1\) に対しても操作 \(i\) をする回数は一意に定まります。

ここで、操作 \(2\) を \(i\) に行う回数を \(B_i\) とした数列 \(B=(B_1,B_2,\dots,B_{N-K+1})\) を固定して目標が達成可能かつその \(B\) になる \(A\) の個数を数え上げます。操作 \(2\) を行う回数が固定されているため、操作 \(1\) で総和の条件を満たす必要があります。

形式的べき級数で表すと、\([x^M]\frac{x^{\sum B}}{(1-x)^N}\) が解となります。これを全ての \(B\) に対して総和を取ると、\([x^{M}]\left(\frac{1-x^K}{1-x}\right) ^{N-K+1} \times \frac{1}{(1-x)^N}\) となります。

上記を整理して、\([x^M] \left(\frac{(1-x^K)^{N-K+1}}{(1-x)^{2N-K+1}}\right)\) を求める問題となります。分子を二項定理で展開することで、\(i=0,1,\dots,N-K+1\) に対して \([x^{M-iK}] \frac{1}{(1-x)^{2N-K+1}}\) を求めればよいです。これは負の二項定理より \(\binom{M+2N-(i+1)K}{2N-K}\) と等しいです。

愚直にこの二項係数を計算しても \(\mathrm{O}(N)\) で計算できるため、\(i=0,1,\dots,N-K+1\) に対しての列挙は \(\mathrm{O}(N^2)\) で可能です。よって、この問題を \(\mathrm{O}(N^2)\) で解くことが出来ました。これは十分高速です。