枚举一个数，容斥，得到答案式子： $$ \begin{aligned} &\sum_{k=1}^n \sum_{i=1}^m (-1)^{i-1} \binom{m}{i} \binom{n-ik-1}{m-i-1}\\ =&\sum_{k=1}^m (-1)^{k-1} \binom{m}{k} \sum_{i=1}^n \binom{n-ik-1}{m-k-1} \end{aligned} $$

一个需要注意的是，插板法要特判 $n=0,m=0$，因此式子要加上 $[m\mid n](-1)^{m-1}$ 才为答案。

枚举 $k$，考虑递推计算后面那项。将组合数改为广义组合数，需要增加上界 $t=\lfloor\frac{n-m+k}{k}\rfloor$。考虑用 $\binom{n}{m}=\sum_{i=0}^k\binom{k}{i}\binom{n-k}{m-i}$ 拆开组合数递推。

令 $f_x=\sum_{i\ge 0}^t\binom{n-ik-1}{x}$，拆开得到： $$ \begin{aligned} f_x&=\sum_{i=1}^t \sum_{j=0}^k \binom{k}{j} \binom{n-(i+1)k-1}{x-j} \\ &=\sum_{j=0}^k \binom{k}{j} \left(f_{x-j} - \binom{n-k-1}{x-j} + \binom{n-(t+1)k-1}{x-j}\right) \\ &=\sum_{j=0}^k \binom{k}{j}f_{x-j} - \sum_{j=0}^k \binom{k}{j}\binom{n-k-1}{x-j} -\sum_{j=0}^k \binom{k}{j}\binom{n-(t+1)k-1}{x-j} \\ &=\sum_{j=0}^k \binom{k}{j}f_{x-j}-\binom{n-1}{x}+\binom{n-tk-1}{x} \\ \end{aligned} $$

因此得到递推式： $$\sum_{j=1}^k\binom{k}{j}f_{x-j}=\binom{n-1}{x}-\binom{n-tk-1}{x}$$ $$f_x=\frac{1}{k} \left( \binom{n-1}{x+1}-\binom{n-tk-1}{x+1}-\sum_{j=1}^{k-1}\binom{k}{j+1}f_{x-j} \right)$$

复杂度 $\mathcal O(m^3)$。