\(O(K)\) で解く解法です。包除原理を用います。

まず、以下の問題について考えます。

\(1\)から \(N\) の整数で構成される集合 \(S\) が与えられます。

長さ \(N\) の整数からなる整数列 \(A\) であって、以下の条件を満たすもの個数を答えよ。

• \(1\leq i \leq N\) について、\(i\in S\) ならば \(M+1\leq A_{i}\) 、そうでないならば \(1\leq A_{i}\)
• \(\sum_{i=1}^{N}A_i \leq K\)

\(|S|=L\) のとき、\(|S|\) として \(\dbinom{N}{L}\) 通り考えられますが、その全てにおいて答えが一致します。

その答えは、 \((K-ML+1)\) 個のボールの間に \(N\) 個の仕切りを仕切りどうしが隣り合わないように置く場合の数と同値で、 \(\dbinom{K-ML}{N}\) となります。 （同値になる理由としては、この仕切られた区間について、右から \(i\) 番目の区間にあるボールの数を \(B_i\) 個として、 \(i\in S\) なら \(A_i=M+B_i\) 、そうでないなら \(A_i=B_i\) とすることで一対一対応を取ることができるからである。)

以上の考察と包除原理より、答えは \(\sum_{L=0}^{N}\dbinom{K-ML}{N}\dbinom{N}{L}(-1)^L\) となります。

事前に \(O(K)\) の計算をすることで二項係数は \(O(1)\) で求まるため、全体の計算量は \(O(K)\) です。