通过二项式，可以得出： bk=∑ni=0ci∗Cki∗biasn−i bk=∑ni=0ci∗i!k!∗(i−k)!∗biasn−i k!∗bk=∑ni=0(ci∗i!)∗biasi−k(i−k)! 看上去可以用FFT快速计算 k!∗bk 建立两个数组 Ai=ci∗i! Bi=biasn−i(n−i)! i>n 时， Ai=Bi=0 可以得到 k!∗bk=∑k+ni=0Ai∗Bk+n−i 然后卷积一下就好了。
#include<bits/stdc++.h> using namespace std; const int MAXN=1<<18; const long long mod=998244353; const int G=3; long long rev[MAXN],w[2][MAXN]; long long fac[MAXN],inv[MAXN]; long long A[MAXN],B[MAXN]; long long pw[MAXN],ipw[MAXN]; long long c[MAXN],ans[MAXN]; int n; long long powmod(long long x,long long p) { long long ret=1; while(p) { if(p&1) ret=ret*x%mod; x=x*x%mod; p>>=1; } return ret; } void init() { fac[0]=1; for(int i=1;i<MAXN;i++) fac[i]=fac[i-1]*i%mod; inv[MAXN-1]=powmod(fac[MAXN-1],mod-2); for(int i=MAXN-2;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod; } void initfft(int n) { int i,k,x,y,v,dv; for(i=0;i<=n-1;i++) { x=i; y=0; for(k=1;k<n;k<<=1,x>>=1) { (y<<=1)|=(x&1); } rev[i]=y; } v=powmod(G,(mod-1)/n); dv=powmod(v,mod-2); w[0][0]=w[1][0]=1; for(i=1;i<=n-1;i++) { w[0][i]=w[0][i-1]*v%mod; w[1][i]=w[1][i-1]*dv%mod; } } inline void fft(long long *A,int n,int ff) { int i,j,k,t,l,v,x,y; for(i=0;i<=n-1;i++) { if(i<rev[i]) swap(A[i],A[rev[i]]); } for(i=1;i<n;i<<=1) { for(j=0,t=n/(i<<1);j<n;j+=(i<<1)) { for(k=0,l=0;k<i;k++,l+=t) { x=A[i+j+k]*w[ff][l]%mod; y=A[j+k]; A[j+k]=(x+y)%mod; A[i+j+k]=(y+mod-x)%mod; } } } if(ff) { v=powmod(n,mod-2); for(i=0;i<=n-1;i++) A[i]=A[i]*v%mod; } } void move(long long *f,int bias,long long *g) { int i,inv_bias,m; if(bias==0) { for(i=0;i<=n;i++) g[i]=f[i]; return; } bias=(mod-bias)%mod; pw[0]=1;//pw[i]表示bias的i次方 for(i=1;i<=n;i++) pw[i]=pw[i-1]*bias%mod; ipw[0]=1;//ipw[i]表示bias的-i次方 inv_bias=powmod(bias,mod-2); for(i=1;i<=n;i++) ipw[i]=ipw[i-1]*inv_bias%mod; m=1; while(m<=2*n+2)//设置m为2的整次幂 m<<=1; for(i=0;i<=m-1;i++) A[i]=B[i]=0; initfft(m);//初始化权值 for(i=0;i<=n;i++) A[i]=f[i]*fac[i]%mod; for(i=0;i<=n;i++) B[n-i]=pw[i]*inv[i]%mod; fft(A,m,0);//正变换 fft(B,m,0); for(i=0;i<=m-1;i++)//卷积 A[i]=A[i]*B[i]%mod; fft(A,m,1);//逆变换 for(i=0;i<=n;i++) g[i]=A[i+n]*inv[i]%mod; } int main() { long long i,m,x,bias; init(); while(~scanf("%d",&n)) { for(i=0;i<=n;i++) scanf("%lld",&c[i]); bias=0; scanf("%lld",&m); for(i=1;i<=m;i++) { scanf("%lld",&x); bias=(bias+x)%mod; } move(c,bias,ans); for(i=0;i<=n;i++) printf("%lld ",ans[i]); puts(""); } }