好菜，之前看了遍题解现在又忘了，还是记录一下吧
求
\[(\sum_{k=0}^nf(k)*x^k*C_n^k)\mod p
\]
\(f(k)\)是\(m\)次多项式，\(f(k)=a_0+a_1k+…+a_mk^m\)
\(n,x,p,a_i\leq1e9,m\leq min(n,1000)\)
SOL:
将\(f(k)\)转成下降幂\(f(k)=\sum_{i=0}^ma_ik^i\to f(k)=\sum_{i=0}^nb_ik^{\underline i}\)
定理：
\[C_n^k*k^\underline m=C_{k-m}^{n-m}*n^\underline m
\]
\[ans=\sum_{k=0}^n\sum_{i=0}^mb_ik^\underline i*x^k*C_n^k
\]
\[ans=\sum_{i=0}^mb_in^\underline i\sum_{k=0}^nC_{n-i}^{k-i}x^k
\]
\[ans=\sum_{i=0}^mb_in^\underline i\sum_{k=0}^{n-i}C_{n-i}^kx^{k+i}
\]
\[ans=\sum_{i=0}^mb_in^\underline ix^i\sum_{k=0}^{n-i}C_{n-i}^kx^{k}
\]
套用二项式定理
\[ans=\sum_{i=0}^mb_in^\underline ix^i(x+1)^{n-i}
\]
于是问题落在普通多项式转下降幂上
\(x^n=\sum_{i=0}^nS_n^ix^\underline i\)
\[\sum_{i=0}^ma_ik^i=\sum_{i=0}^ma_i\sum_{j=0}^iS_i^jk^\underline j
\]
\[=\sum_{j=0}^mk^\underline j\sum_{i=j}^mS_i^ja_i
\]
//starusc
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;char c=getchar();
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
return f==1?x:-x;
}
#define ll long long
const int N=1004;
int n,t,p,m,ans,s[N][N],a[N],b[N];
inline int ksm(int x,int r){
int ret=1;
for(int i=0;(1ll<<i)<=r;i++){
if((r>>i)&1)ret=(ll)ret*x%p;
x=(ll)x*x%p;
}
return ret;
}
int main(){
n=read();t=read();p=read();m=read();
for(int i=0;i<=m;i++)a[i]=read();
s[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=1;j<=i;j++)s[i][j]=((ll)s[i-1][j]*j+s[i-1][j-1])%p;
for(int i=0;i<=m;i++)
for(int j=i;j<=m;j++)b[i]=((ll)s[j][i]*a[j]+b[i])%p;
for(int i=0,pwt=1,unn=1;i<=m;unn=(ll)unn*(n-i)%p,i++,pwt=(ll)pwt*t%p)
ans=((ll)b[i]*pwt%p*unn%p*ksm(t+1,n-i)+ans)%p;
cout<<ans;
return (0-0);
}
类似题目：UOJ269如何优雅地求和
