引入
求出满足 的多项式 。
做法
既然可以快速幂求 ,其实多项式也是可以的。那么总的复杂度为 其实这个好写,常数也小,一般不会被卡。
我们可以对一个多项式求 和 。那么 求出 。之后在做一次 就可以了。记住,如果 下面给出的代码并不能通过。
代码
#include<bits/stdc++.h> using namespace std; const int N = 4e6 + 100,P = 998244353; int limit,r[N],L; int ksm(int a,int b) {int x=1;for(;b;b>>=1,a=1LL*a*a%P)if(b&1)x=1LL*x*a%P;return x;} void NTT(int *a,int type) { for(int i=0;i<limit;i++)if(i>r[i])swap(a[i],a[r[i]]); for(int mid=1;mid<limit;mid<<=1) { int wn=ksm(3,(P-1)/(mid<<1));for(int i=0;i<limit;i+=(mid<<1)){ for(int j=0,w=1;j<mid;j++,w=1LL*w*wn%P) { int x=a[i+j],y=1LL*a[i+j+mid]*w%P; a[i+j]=(x+y)%P;a[i+j+mid]=(x-y+P)%P; } } } if(type==-1) {reverse(a+1,a+limit);int Inv=ksm(limit,P-2);for(int i=0;i<limit;i++)a[i]=1LL*a[i]*Inv%P;} } void Mul(int *f,int *g,int len) { static int G[N]; memcpy(G,g,sizeof(G)); NTT(f,1);NTT(g,1); for(int i = 0;i < limit;i++) f[i] = 1LL * f[i] * g[i] % P; NTT(f,-1);for(int i=len+1;i<limit;i++) f[i]=0; } void init(int len) { limit=1;L=0;while(limit<=len)limit<<=1,L++; for(int i=0;i<limit;i++)r[i]=(r[i>>1]>>1)|((i&1)<<L-1); } void GetInv(int *f,int *g,int n) { if(n==1) {g[0]=ksm(f[0],P-2);return;} GetInv(f,g,(n+1)>>1); init(n+n-2); static int c[N];memset(c,0,sizeof(c)); for(int i = 0;i < n;i++) c[i] = f[i]; NTT(c,1);NTT(g,1); for(int i = 0;i < limit;i++) g[i] = 1LL * g[i] * ((2LL - 1LL * c[i] * g[i] % P + P) % P) % P; NTT(g,-1);for(int i = n;i < limit;i++) g[i] = 0; } void Dao(int *f,int *g,int n) { for(int i = 1;i < n;i++) g[i-1]=1LL*f[i]*i%P;g[n-1]=0; } void JiFen(int *f,int *g,int n) { for(int i = 1;i < n;i++) g[i]=1LL*f[i-1]*ksm(i,P-2)%P;g[0]=0; } void GetLn(int *f,int *g,int n) { static int A[N],B[N];memset(A,0,sizeof(A));memset(B,0,sizeof(B)); Dao(f,A,n);GetInv(f,B,n); init(n+n-2);NTT(A,1);NTT(B,1); for(int i=0;i<limit;i++)A[i]=1LL*A[i]*B[i]%P; NTT(A,-1);JiFen(A,g,n); } void GetExp(int *f,int *g,int n) { if(n==1) {g[0]=1;return;} GetExp(f,g,(n+1)>>1);static int F[N]; memset(F,0,sizeof(F));GetLn(g,F,n); F[0]=(1LL*f[0]+1-F[0]+P)%P; for(int i=1;i<n;i++)F[i]=(-1LL*F[i]+f[i]+P)%P; init(n+n-2);Mul(g,F,n-1); } void GetPow(int *f,int *g,int n,int K) { static int F[N];memset(F,0,sizeof(F)); GetLn(f,F,n); for(int i=0;i<n;i++)F[i]=1LL*K*F[i]%P; GetExp(F,g,n); } int f[N],g[N]; int readMod(int mod) { int x=0;char ch=getchar();while(!isdigit(ch))ch=getchar(); while(isdigit(ch)){x=(10LL*x+ch-'0')%mod;ch=getchar();} return x; } int main() { int n,K; cin >> n;K=readMod(P);for(int i = 0;i < n;i++) cin >> f[i]; GetPow(f,g,n,K); for(int i = 0;i < n;i++) cout << g[i] << " "; return 0; }