多项式快速幂
时间限制 : 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 #include #include #include #include #include #define ll long long using 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;ifor(j=0,k=i,m=1;m1,j=(j<<1)|(k&1),k>>=1); if(i0]=1; for(m=1;m1){ t0=mont(g,p-1+ty*(p-1)/(m<<1)); for(i=1;i1LL*fft_wi[i-1]*t0%p; for(k=0;k1)){ for(i=k;i1LL*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;i1LL*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;ifor(i=0;i1; while(N<=(la+lb+1))N<<=1; fft(d,N,1); fft(e,N,1); for(i=0;i1ll*d[i]*e[i]%p; fft(d,N,-1); for(i=0;i1;i++)C[i]=d[i]; for(i=la+lb-1;i0; } 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;m1){ n=m<<1; for(i=0;ifor(n<<=1;i0; for(i=m;i0; fft(inv_c,n,1); fft(B,n,1); for(i=0;i2-1ll*inv_c[i]*B[i]%p; for(i=0;ifor(i=0;i1ll*B[i]*inv_c[i]%p; fft(B,n,-1); } for(i=lb;i0; } 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(n1; memset(ln_c,0,sizeof(ln_c)); memset(ln_d,0,sizeof(ln_d)); memset(ln_e,0,sizeof(ln_e)); for(i=0;ifor(i=1;i1]=1ll*A[i]*i%p; for(i=la-1;i0; multi(ln_d,ln_c,ln_e,n,la-1); for(i=2,ln_c[1]=1;i1ll*(p-p/i)*ln_c[p%i]%p; for(i=1;i1ll*ln_e[i-1]*ln_c[i]%p; B[0]=0; for(i=lb;i0; } 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;m1){ n=(m<<1); ln(B,exp_c,m,n); exp_d[0]=1; for(i=1;i0; for(i=0;ifor(i=0;iif(exp_d[i]>=p)exp_d[i]-=p; for(i=0;ifor(i=0;iif(exp_d[i]<0)exp_d[i]+=p; multi(B,exp_d,exp_c,m,n); for(i=0;iint 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;i1ll*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;icin>>k>>lb; poly_mont(a,b,k,la,lb); for(i=0;iprintf("%d ",b[i]); } }