多项式快速幂 时间限制 : 60000 MS 空间限制 : 524288 KB
问题描述：
给一个n次多项式，求它的k次方。没关系，随手模一个998244353就行了。没关系，再随手模一个xm就行了。
输入格式：
第一行n，意义如上。 第二行n+1个数，a0,a1,…,an，分别是0,1,…,n次项系数。 第三行k，意义如上。 第四行m，意义如上。
输出格式
一行，b0,b1,…,bm-1，分别是0,1,…,m-1次项系数。
样例输入
1 1 1 5 2
样例输出
1 5
提示
样例解释： (1+x)5 =1+5x+10x2+10x3+5x4+x5 ≡1+5x (mod x2)
数据范围： n,m<=100000 k<=1018
求逆元和exp的时候要使用牛顿迭代。 
#include<iostream>#include<cstdio>#include<algorithm>#include<cstdlib>#include<cstring>#include<complex>#define ll long longusing namespace std;template <typename T>inline void _read(T& x){ char t=getchar();bool sign=true; while(t<'0'||t>'9') {if(t=='-')sign=false;t=getchar();} for(x=0;t>='0'&&t<='9';t=getchar())x=x*10+t-'0'; if(!sign)x=-x;}const int p=998244353;const int g=3;int mont(int x,int y){ ll ANS=1; for(x%=p;y;y>>=1,x=1LL*x*x%p){ if(y&1)ANS=1LL*ANS*x%p; } return int(ANS); }int fft_wi[300005];void fft(int A[],int n,int ty){ int i,j,k,m,t0,t1; for(i=0;i<n;i++){ for(j=0,k=i,m=1;m<n;m<<=1,j=(j<<1)|(k&1),k>>=1); if(i<j)swap(A[i],A[j]); } fft_wi[0]=1; for(m=1;m<n;m<<=1){ t0=mont(g,p-1+ty*(p-1)/(m<<1)); for(i=1;i<m;i++)fft_wi[i]=1LL*fft_wi[i-1]*t0%p; for(k=0;k<n;k+=(m<<1)){ for(i=k;i<k+m;i++){ t0=A[i]; t1=1LL*A[i+m]*fft_wi[i-k]%p; A[i]=t0+t1;if(A[i]>=p)A[i]-=p; A[i+m]=t0-t1;if(A[i+m]<0)A[i+m]+=p; } } } if(ty==1)return; t0=mont(n,p-2); for(i=0;i<n;i++){ A[i]=1LL*A[i]*t0%p; } }int d[300005],e[300005];void multi(int A[],int B[],int C[],int la,int lb){ int i,j,k,t,N; memset(d,0,sizeof(d)); memset(e,0,sizeof(e)); for(i=0;i<la;i++)d[i]=A[i]; for(i=0;i<lb;i++)e[i]=B[i]; N=1; while(N<=(la+lb+1))N<<=1; fft(d,N,1); fft(e,N,1); for(i=0;i<N;i++)d[i]=1ll*d[i]*e[i]%p; fft(d,N,-1); for(i=0;i<la+lb-1;i++)C[i]=d[i]; for(i=la+lb-1;i<N;i++)C[i]=0;}int inv_c[300005];void inv(int A[],int B[],int la,int lb){ memset(inv_c,0,sizeof(inv_c)); int i,j,k,t,n,m; B[0]=mont(A[0],p-2); for(m=1;m<lb;m<<=1){ n=m<<1; for(i=0;i<n;i++)inv_c[i]=A[i]; for(n<<=1;i<n;i++)inv_c[i]=0; for(i=m;i<n;i++)B[i]=0; fft(inv_c,n,1); fft(B,n,1); for(i=0;i<n;i++)inv_c[i]=p+2-1ll*inv_c[i]*B[i]%p; for(i=0;i<n;i++)inv_c[i]=(inv_c[i]%p+p)%p; for(i=0;i<n;i++)B[i]=1ll*B[i]*inv_c[i]%p; fft(B,n,-1); } for(i=lb;i<n;i++)B[i]=0;}int ln_c[300005],ln_d[300005],ln_e[300005];void ln(int A[],int B[],int la,int lb){ int i,j,k,t,n; n=1; while(n<la||n<lb)n<<=1; memset(ln_c,0,sizeof(ln_c)); memset(ln_d,0,sizeof(ln_d)); memset(ln_e,0,sizeof(ln_e)); for(i=0;i<la;i++)ln_c[i]=A[i]; inv(ln_c,ln_d,la,n); for(i=1;i<la;i++)ln_c[i-1]=1ll*A[i]*i%p; for(i=la-1;i<n;i++)ln_c[i]=0; multi(ln_d,ln_c,ln_e,n,la-1); for(i=2,ln_c[1]=1;i<lb;i++)ln_c[i]=1ll*(p-p/i)*ln_c[p%i]%p; for(i=1;i<lb;i++)B[i]=1ll*ln_e[i-1]*ln_c[i]%p; B[0]=0; for(i=lb;i<n;i++)B[i]=0;}int exp_c[300005],exp_d[300005];void exp(int A[],int B[],int la,int lb){ int i,j,k,t,n,m; for(m=1;m<lb;m<<=1){ n=(m<<1); ln(B,exp_c,m,n); exp_d[0]=1; for(i=1;i<n;i++)exp_d[i]=0; for(i=0;i<n;i++)exp_d[i]+=A[i]; for(i=0;i<n;i++)if(exp_d[i]>=p)exp_d[i]-=p; for(i=0;i<n;i++)exp_d[i]-=exp_c[i]; for(i=0;i<n;i++)if(exp_d[i]<0)exp_d[i]+=p; multi(B,exp_d,exp_c,m,n); for(i=0;i<n;i++)B[i]=exp_c[i]; }}int poly_d[300005],poly_e[300005];void poly_mont(int A[],int C[],ll num,int la,int lc){ int i,j,k,t,N,ld,le; ln(A,poly_d,la,lc); t=num%p; for(i=0;i<lc;i++)poly_d[i]=1ll*poly_d[i]*t%p; C[0]=mont(A[0],num%(p-1)); exp(poly_d,C,lc,lc); }int a[300005],b[300005];int main(){ int i,j,la,lb; ll k; cin>>la;la++; for(i=0;i<la;i++){ _read(a[i]); } cin>>k>>lb; poly_mont(a,b,k,la,lb); for(i=0;i<lb;i++){ PRintf("%d ",b[i]); }}
