题目描述
众所周知，小葱同学擅长计算，尤其擅长计算组合数。小葱现在希望你计算
\[\left(\sum_{k=0}^{n}f(k)\times x^k\times \binom{n}{k}\right)\bmod p
\]
的值。其中 \(n\), \(x\), \(p\) 为给定的整数，\(f(k)\) 为给定的一个 \(m\) 次多项式 \(f(k) = a_0 + a_1k + a_2k^2 + \cdots + a_mk^m\)。
\(\binom{n}{k}\) 为组合数，其值为 \(\binom{n}{k} = \frac{n!}{k!(n-k)!}\)。
数据范围
对于所有测试数据：\(1\le n, x, p \le 10^9, 0\le a_i\le 10^9, 0\le m \le \min(n,1000)\)。
题解
前置知识
我们考虑这样一个下降幂单项式：
\[k^\underline{m}=\prod_{i=k-m+1}^ki
\]
让它和组合数相乘，会得到一个优美的式子：
\[\binom{n}{k}\times k^\underline{m}=\binom{n-m}{k-m}\times n^\underline{m}
\]
证明的话是显然的，把组合数展开约一下分就好了。
本题解法
那么题目中的 \(f(x)\) 可以转化为下降幂多项式：
\[\begin{aligned}
f(k)&=\sum_{i=0}^ma_ik^i\&=\sum_{i=0}^mb_ik
\end{aligned}
\]
则题目中的式子
\[\begin{aligned}
\sum_{k=0}^nf(k)\times x^k\times \binom{n}{k}
&=\sum_{k=0}^n\sum_{i=0}^ma_ik^i\times x^k\times \binom{n}{k}\&=\sum_{k=0}^n\sum_{i=0}^mb_ik^\underline{i}\times x^k\times \binom{n}{k}\&=\sum_{i=0}^mb_in^\underline{i}\sum_{k=0}^n\binom{n-i}{k-i}x^k
\end{aligned}
\]
发现如果 \(i>k\) 的话，里面的值就直接为 \(0\) 了，于是内层求和改成枚举 \(k-i\)：
\[\sum_{i=0}^mb_in^\underline{i}\sum_{k=0}^{n-i}\binom{n-i}{k}x^{k+i}=\sum_{i=0}^mb_in^\underline{i}x^i\sum_{k=0}^{n-i}\binom{n-i}{k}x^k
\]
套一下我们小学二年级（雾）就学过的二项式定理：
\[\begin{aligned}
\sum_{k=0}^{n-i}\binom{n-i}{k}x^k
&=\sum_{k=0}^{n-i}\binom{n-i}{k}x^k1^{n-i-k}\&=(x+1)^{n-i}
\end{aligned}
\]
于是题目的式子就变成了
\[\sum_{i=0}^mb_in^\underline{i}x^i(x+1)^{n-i}
\]
而
\[x^n=\sum_{i=0}^n\begin{Bmatrix}n\\i\end{Bmatrix}x^\underline{i}
\]
所以有：
\[\begin{aligned}
\sum_{i=0}^ma_ik^i&=\sum_{i=0}^ma_i\sum_{j=0}^i\begin{Bmatrix}i\\j\end{Bmatrix}k^\underline{j}\&=\sum_{i=0}^mk^\underline{i}\sum_{j=0}^i\begin{Bmatrix}j\\i\end{Bmatrix}a_j
\end{aligned}
\]
也就是说
\[b_i=\sum_{j=i}^m\begin{Bmatrix}j\\i\end{Bmatrix}a_j
\]
\(\Theta(m^2)\) 暴力递推第二类 \(\texttt{stirling}\) 数即可，总时间复杂度 \(\Theta(m^2)\)