给定 \(n,m,k\) 已知,求满足以下式子的自然数序列 \(a\) 的数目:
- \(\sum_{i=1}^nx_i=m\)
- \(x_i\in [0,k)\)
考虑 dp,设 \(f_{i,j}\) 为前 \(i\) 个数和为 \(j\) 的方案数:
\[f_{i,j}=\sum_{p=0}^{k-1}f_{i-1,j-p}
\]
然后可以看作生成函数 \(g=\sum_{i=0}^{k-1}x^i=\frac {1-x^k}{1-x}\) 和 \(f_{i-1}\) 的卷积
然后 \(f_{1,i}=1\),所以 \(f_1=g\)
所以:
\[ans=[x^m]f_n=[x^m]g^n=[x^m](\frac {1-x^k}{1-x})^n\\
=[x^m](1-x^k)^n\times (\frac 1 {1-x})^n\\
=[x^m]\sum_{i=0}^n \binom n i(-1)^ix^{ik}\times (\sum_{i=0}\binom {i+n-1} {n-1}x^i)\\
\sum_{i=0}^n \binom n i (-1)\binom {m-ki+n-1}{n-i}
\]
然后就可以做到 \(O(n+m)\) ,而且比较好想,比容斥什么的不知道高到哪去了