Description Input 多组用例，每组用例首先输入一整数n表示f的次数，之后输入n+1个整数c[i]表示f的系数，然后输入一整数m，之后输入m个整数a[i]，以文件尾结束输入 (n<=1e5,0<=a[i],c[i]<998244353,sum{m}<=1e5) Output 对于每组用例，输出b[0]~b[n] Sample Input 2 0 0 1 1 1 Sample Output 1 998244351 1 Solution Code
#include<bits/stdc++.h> using namespace std; typedef long long ll; const int maxbit=18,maxlen=1<<maxbit,mod=998244353,g=3,maxn=100001; int wn[maxlen],inv2[maxbit+1],fact[maxn],inv[maxn]; int mod_pow(int a,int b) { int ans=1; while(b) { if(b&1)ans=(ll)ans*a%mod; a=(ll)a*a%mod; b>>=1; } return ans; } void init() { wn[0]=1,wn[1]=mod_pow(g,(mod-1)>>maxbit); for(int i=2;i<maxlen;i++)wn[i]=(ll)wn[i-1]*wn[1]%mod; inv2[0]=1,inv2[1]=(mod+1)/2; for(int i=2;i<=maxbit;i++)inv2[i]=(ll)inv2[i-1]*inv2[1]%mod;//预处理2^i的逆元 fact[0]=1; for(int i=1;i<maxn;i++)fact[i]=(ll)i*fact[i-1]%mod;//求i! inv[0]=inv[1]=1; for(int i=2;i<maxn;i++)inv[i]=mod-(int)(mod/i*(ll)inv[mod%i]%mod);//线性求1~n逆元 for(int i=1;i<maxn;i++)inv[i]=(ll)inv[i-1]*inv[i]%mod;//预处理i!的逆元 } void ntt(int *x,int len,int sta) { for(int i=0,j=0;i<len;i++) { if(i>j)swap(x[i],x[j]); for(int l=len>>1;(j^=l)<l;l>>=1); } for(int i=1,d=1;d<len;i++,d<<=1) for(int j=0;j<len;j+=d<<1) for(int k=0;k<d;k++) { int t=(ll)wn[(maxlen>>i)*k]*x[j+k+d]%mod; x[j+d+k]=x[j+k]-t<0?x[j+k]-t+mod:x[j+k]-t; x[j+k]=x[j+k]+t>=mod?x[j+k]+t-mod:x[j+k]+t; } if(sta==-1) { reverse(x+1,x+len); int bitlen=0; while((1<<bitlen)<len)bitlen++; int val=inv2[bitlen]; for(int i=0;i<len;i++)x[i]=(ll)x[i]*val%mod; } } void NTT(int *a,int *b,int len1,int len2) { int len=1; while(len<len1+len2)len<<=1; for(int i=len1;i<len;i++)a[i]=0; for(int i=len2;i<len;i++)b[i]=0; ntt(a,len,1),ntt(b,len,1); for(int i=0;i<len;i++)a[i]=(ll)a[i]*b[i]%mod; ntt(a,len,-1); } int n,m,c[maxn],a; int A[maxlen],B[maxlen]; int main() { init(); while(~scanf("%d",&n)) { for(int i=0;i<=n;i++)scanf("%d",&c[i]); scanf("%d",&m); a=0; for(int i=0;i<m;i++) { int t; scanf("%d",&t); a+=t; if(a>=mod)a-=mod; } int temp=1; A[0]=1; for(int i=1;i<=n;i++) { temp=(ll)temp*a%mod; temp=mod-temp; A[i]=(ll)temp*inv[i]%mod; } for(int i=0;i<=n;i++)B[i]=(ll)c[n-i]*fact[n-i]%mod; NTT(A,B,n+1,n+1); for(int i=0;i<=n;i++)A[i]=(ll)A[i]*inv[n-i]%mod; for(int i=0;i<=n;i++)printf("%d ",A[n-i]); printf("\n"); } }