将$f(k)=\sum_{i=0}^{m}a_{i}k^{i}$转换为$f(k)=\sum_{i=0}^{m}b_{i}k^{\underline{i}}$，其中$k^{\underline{i}}=\frac{k!}{(k-i)!}$
题目即求$\sum_{k=0}^{n}c(n,k)x^{k}\sum_{i=0}^{m}b_{i}\cdot k^{\underline{i}}$
调整枚举顺序，即$\sum_{i=0}^{m}b_{i}\sum_{k=0}^{n}c(n,k)x^{k}k^{\underline{i}}$
观察发现$c(n,k)k^{\underline{i}}=\frac{n!}{k!(n-k)!}\frac{k!}{(k-i)!}=\frac{n!}{(k-i)!(n-k)!}=c(n-i,k-i)n^{\underline{i}}$
代入原式，即$\sum_{i=0}^{m}b_{i}n^{\underline{i}}\sum_{k=0}^{n}c(n-i,k-i)x^{k}$
令$k‘=k-i$，即$\sum_{i=0}^{m}b_{i}n^{\underline{i}}x^{i}\sum_{k‘=0}^{n-i}c(n-i,k‘)x^{k‘}$
观察发现右式即$(x+1)^{n-i}$二项式展开，那么即$\sum_{i=0}^{m}b_{i}n^{\underline{i}}x^{i}(x+1)^{n-i}$
那么问题变为如何求出$b_{i}$，即如何将多项式转换为下降幂多项式【luoguP5383】
根据第二类斯特林数的性质，有$x^{n}=\sum_{i=0}^{n}c(x,i)i!S(n,i)=\sum_{i=0}^{n}S(n,i)x^{\underline{i}}$
那么就有$\sum_{i=0}^{m}a_{i}x^{i}=\sum_{i=0}^{m}a_{i}\sum_{j=0}^{i}S(i,j)x^{\underline{j}}=\sum_{j=0}^{m}x^{\underline{j}}\sum_{i=j}^{m}a_{i}S(i,j)$，即$b_{j}=\sum_{i=j}^{m}a_{i}S(i,j)$
本题由于$m\le 1000$，仅需要根据$S$的递推式暴力求出$S$并$o(m^{2})$计算即可
1 #include<bits/stdc++.h>
2 using namespace std;
3 #define N 1005
4 int n,x,mod,m,ans,a[N],b[N],s[N][N];
5 int ksm(int n,int m){
6 if (!m)return 1;
7 int s=ksm(n,m>>1);
8 s=1LL*s*s%mod;
9 if (m&1)s=1LL*s*n%mod;
10 return s;
11 }
12 int main(){
13 scanf("%d%d%d%d",&n,&x,&mod,&m);
14 for(int i=0;i<=m;i++)scanf("%d",&a[i]);
15 s[0][0]=1;
16 for(int i=1;i<=m;i++)
17 for(int j=1;j<=i;j++)s[i][j]=(s[i-1][j-1]+1LL*j*s[i-1][j])%mod;
18 for(int i=0;i<=m;i++)
19 for(int j=i;j<=m;j++)b[i]=(b[i]+1LL*a[j]*s[j][i])%mod;
20 int s=1;
21 for(int i=0;i<=m;i++){
22 ans=(ans+1LL*b[i]*s%mod*ksm(x,i)%mod*ksm(x+1,n-i))%mod;
23 s=1LL*s*(n-i)%mod;
24 }
25 printf("%d",ans);
26 }
View Code
[loj3300]组合数问题
原文：https://www.cnblogs.com/PYWBKTDA/p/13409749.html
