题解 P6620 【[2020 年联考 A 卷] 组合数问题【暂无数据】】
Rorschachindark
·
·
题解
组合数问题
题目传送门
题目大意
给出一个m次多项式，a_0x+a_1x+...+a_mx^m，再给出n,x,m,p，请求出:
\sum_{k=0}^{n} f(k)x^k \binom{n}{k}
n,x,p\le 10^9,m\le 10^3
思路
考场sb了，式子推出来没看到j!\times \binom{n}{j}，然后就炸了。
言归正传，我们显然应该将多项式系数展开，因为不展开就一定时间复杂度与n有关系，于是就可以得到答案为:
\sum_{i=0}^{m} a_i \sum_{k=0}^{n} k^i x^k \binom{n}{k}
很显然，这个时候我们应该将k^i用第二类斯特林数展开，于是得到:
=\sum_{i=0}^{m} a_i\sum_{k=0}^{n} x^k \binom{n}{k} \sum_{j=0}^{k} \begin{Bmatrix} i\\j\end{Bmatrix}\binom{k}{j}j!
调换求和顺序又利用:
\binom{n}{m}\binom{m}{k}=\binom{n}{k}\binom{n-k}{m-k}
可以得到:
=\sum_{i=0}^{m} a_i\sum_{j=0}^{i} \begin{Bmatrix} i\\j\end{Bmatrix}j!\binom{n}{j}\sum_{k=0}^{n-j}x^{k+j} \binom{n-j}{k}
又因为:
(1+x)^n=\sum_{i=0}^{n} x^i \binom{n}{i}
所以得到:
=\sum_{i=0}^{m} a_i\sum_{j=0}^{i} \begin{Bmatrix} i\\j\end{Bmatrix}j!\binom{n}{j} x^j(1+x)^{n-j}
考试的时候sb了，没看到\binom{n}{j}j!。于是可以得到:
=\sum_{i=0}^{m} a_i \sum_{j=0}^{i} \begin{Bmatrix} i\\j\end{Bmatrix}x^j(1+x)^{n-j}n^{\underline{j}}
因为第二类斯特林数有一个递推公式:
\begin{Bmatrix} n\\m\end{Bmatrix}=\begin{Bmatrix} n-1\\m-1\end{Bmatrix}+m\begin{Bmatrix} n-1\\m\end{Bmatrix}
所以我们就可以\Theta(m^2)预处理出\begin{Bmatrix} i\\j\end{Bmatrix}。
至此，我们可以\Theta(m^2)解决这个问题，做完了可以去看一下这道题。两道题是差不多的。