题目链接
https://www.luogu.com.cn/problem/P6620
题解
本题要求我们求出：
$$
\sum_{k=0}^{n}f(k)\times x^k\times C_n^k
$$
其中 \(f(k)\) 为一个次数为 \(m\) 的普通多项式 \(\sum_{i=0}^m a_ix^i\)。
在介绍解法之前，我们先给出若干定义和引理（熟悉的同学可直接跳过这些内容）：
定义 1：定义 \(x\) 的 \(k\) 次下降幂 \(x^{\underline{k}}=\frac{x!}{(x-k)!}\)，这也被称为一个关于 \(x\) 的下降幂单项式。
定义 2：定义下降幂多项式为有限多下降幂单项式的和，形如 \(\sum_{i=0}^k a_ix^{\underline{i}}\)。与之相对应的是，形如 \(\sum_{i=0}^k a_ix^i\) 的多项式，我们称为普通多项式。
定义 3：我们定义第二类斯特林数 \(\begin{Bmatrix}n\\m\end{Bmatrix}\) 为将 \(n\) 个完全相同的元素，不重不漏地划分成 \(m\) 个集合的方案数。
说完了定义，我们接下来给出若干引理和定理：
定理 0（二项式定理）：\((x+y)^k=\sum_{i=0}^k C_k^i x^iy^{k-i}\)。
考虑组合意义即可得证。
定理 1.1：\(m \times C_n^m=n \times C_{n-1}^{m-1}\)。
高中学过组合数学的同学可能都熟悉这个性质。只需将两边的组合数全部展开为阶乘形式即可得证。
事实上上面这个定理可以进一步推广到下降幂的情形（也就是下面的 定理 1.2）：
定理 1.2：\(m^{\underline{k}} \times C_{n}^{m}=n^{\underline{k}} \times C_{n-k}^{m-k}\)。
证明仍然是直接展开等式两边，这里略去。
引理 1：\(x^k=\sum_{i=0}^k \begin{Bmatrix}k\\i\end{Bmatrix} x^{\underline{i}}\)。
证明从略。
利用这个引理，我们可以给出普通多项式转化为下降幂多项式的方法（也就是下面的 定理 2）：
定理 2：记普通多项式 \(f(x)=\sum_{i=0}^k a_ix^{i}\)，下降幂多项式 \(g(x)=\sum_{i=0}^k b_ix^{\underline{i}}\)，且 \(f(x)=g(x)\)，则有 \(b_i=\sum_{j=i}^k \begin{Bmatrix}j\\i\end{Bmatrix}a_j\)。
证明考虑根据 引理 1 将普通多项式展开：
$$
\begin{aligned}
\sum_{i=0}^k a_ix^i &= \sum_{i=0}^k a_i \sum_{j=0}^i \begin{Bmatrix}i\\j\end{Bmatrix} x^{\underline{j}}\\
&= \sum_{i=0}^k x^{\underline{i}}\sum_{j=i}^k \begin{Bmatrix}j\\i\end{Bmatrix} a_j
\end{aligned}
$$
定理 3（第二类斯特林数递推公式）：\(\begin{Bmatrix}n\\m\end{Bmatrix}=m\times \begin{Bmatrix}n-1\\m\end{Bmatrix}+\begin{Bmatrix}n-1\\m-1\end{Bmatrix}\)
还是考虑组合意义：对于每个新增的元素，我们可以将其放在原有的集合中，或者是单独安排一个集合。
利用该定理，我们可以在 \(O(n^2)\) 时间内递推出我们需要的第二类斯特林数的值。
接下来进入正题。
我们发现一个普通多项式与组合数相乘并没有什么显然的性质，而定理 1.2 则告诉了我们下降幂多项式与组合数相乘的性质。因此考虑根据 定理 2，将普通多项式 \(f(x)=\sum_{i=0}^k a_ix^{i}\) 转化为下降幂多项式 \(g(x)=\sum_{i=0}^k b_ix^{\underline{i}}\)。
也就是说我们所求变成了：
$$
\sum_{k=0}^{n}g(k)\times x^k\times C_n^k
$$
现在利用 定理 1.2 改写上式：
$$
\begin{aligned}
\sum_{k=0}^{n}g(k)\times x^k\times C_n^k &= \sum_{k=0}^{n}\sum_{i=0}^m b_i \times k^{\underline{i}}\times x^k\times C_n^k\\
&= \sum_{k=0}^{n}x^k\sum_{i=0}^m b_i \times n^{\underline{i}} \times C_{n-i}^{k-i}\\
&= \sum_{i=0}^{m}b_i \times n^{\underline{i}} \sum_{k=0}^n C_{n-i}^{k-i} x^k\\
\end{aligned}
$$
注意到只有 \(k-i \geq 0\) 的时候才会对答案产生贡献，考虑枚举 \(k-i\) 的值，为了避免混淆，令 \(k’=k-i\)：
$$
\begin{aligned}
\sum_{i=0}^{m}b_i \times n^{\underline{i}} \sum_{k’=0}^{n-i} C_{n-i}^{k’} x^{k’+i} &= \sum_{i=0}^{m}b_i \times n^{\underline{i}} \times x^i \sum_{k’=0}^{n-i} C_{n-i}^{k’} x^{k’}\\
&= \sum_{i=0}^{m}b_i \times n^{\underline{i}} \times x^i \times (x+1)^{n-i}
\end{aligned}
$$
最后一步推导实际上就是二项式定理的逆用。
到这里本题就做完了。
上式可以 \(O(m)\) 来计算，而本题时间瓶颈主要在递推求第二类斯特林数上，这部分的时间复杂度为 \(O(m^2)\)。
// Problem : P6620 [省选联考 2020 A 卷] 组合数问题
// Contest : Luogu
// URL : https://www.luogu.com.cn/problem/P6620
// Memory Limit : 512 MB
// Time Limit : 1000 ms
// Powered by CP Editor (https://github.com/cpeditor/cpeditor)
#include <iostream>
using namespace std;
int n,x,p,m;
long long a[1005],b[1005];
long long s[1005][1005];
long long f[1005],g[1005],h[1005];
long long fpow(long long x,long long y)
{
long long ans=1;
while(y)
{
if(y&1)ans=ans*x%p;
x=x*x%p;
y>>=1;
}
return ans;
}
int main()
{
cin>>n>>x>>p>>m;
for(int i=0;i<=m;i++)
cin>>a[i];
s[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=1;j<=i;j++)
s[i][j]=(j*s[i-1][j]+s[i-1][j-1])%p;
for(int i=0;i<=m;i++)
for(int j=i;j<=m;j++)
b[i]=(b[i]+s[j][i]*a[j])%p;
f[0]=1,g[0]=1,h[m]=fpow(x+1,n-m);
for(int i=1;i<=m;i++)
{
f[i]=f[i-1]*(n-i+1)%p;
g[i]=g[i-1]*x%p;
}
for(int i=m-1;i>=0;i--)
h[i]=h[i+1]*(x+1)%p;
long long ans=0;
for(int i=0;i<=m;i++)
ans=(ans+b[i]*f[i]%p*g[i]%p*h[i])%p;
cout<<ans<<endl;
return 0;
}