省选联考2020组合数问题

好菜，之前看了遍题解现在又忘了，还是记录一下吧

求

\(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}\)

定理：

套用二项式定理

于是问题落在普通多项式转下降幂上

\(x^n=\sum_{i=0}^nS_n^ix^\underline 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如何优雅地求和

省选联考2020组合数问题

原文：https://www.cnblogs.com/aurora2004/p/13228410.html