贴个板子,以备复习
#include<cstdio> #include<cstdlib> #include<algorithm> #include<unordered_map> #include<cmath> #define mod 998244353 #define maxn 400010 #define ll long long #define it unordered_map<ll,int>::iterator using namespace std; int pos[maxn]; ll A[maxn],B[maxn],C[maxn],w[maxn],D[maxn],E[maxn],P[maxn],Q[maxn],iB[maxn]; ll qpow(ll x,int p){ ll base,ans; for(base=x,ans=1;p;p>>=1,base=base*base%mod){ if(p&1) ans=ans*base%mod; } return ans; } ll inv(ll x){ return qpow(x,mod-2); } namespace discrete_sqrt{ unordered_map<long long,int> M; int BSGS(ll x){ int i,N; N=(int)(ceil(sqrt(mod-0.5))); ll w,w0=qpow(3,N); for(i=0,w=1;i<N;++i,w=w*3%mod){ M[x*w%mod]=i; } for(i=1,w=w0;i<=N;w=w*w0%mod,++i){ it t=M.find(w); if(t!=M.end()) return i*N-(t->second); } return -1; } ll sqr(ll x){ int u=BSGS(x); ll ans=qpow(3,u/2); return min(ans,mod-ans); } } void NTT(ll *L,int N,int type,int lg){ int i,j,t,d; for(i=0;i<N;++i) pos[i]=pos[i>>1]>>1|((1&i)<<lg-1); w[0]=1,w[1]=type>0?qpow(3,(mod-1)>>lg):inv(qpow(3,(mod-1)>>lg)); for(i=2;i<N;++i) w[i]=w[i-1]*w[1]%mod; for(i=0;i<N;++i){ if(pos[i]>i) swap(L[i],L[pos[i]]); } for(t=1,d=N>>1;t<N;d>>=1,t<<=1){ for(i=0;i<N;i+=t<<1){ for(j=0;j<t;++j){ ll tmp=w[j*d]*L[i+j+t]%mod; L[i+j+t]=(L[i+j]+mod-tmp)%mod; L[i+j]=(L[i+j]+tmp)%mod; } } } } void poly_diff(ll *L,int N){ for(int i=0;i<N;++i) L[i]=L[i+1]*(i+1)%mod; L[N-1]=0; } void poly_int(ll *L,int N){ for(int i=N;i>0;--i) L[i]=L[i-1]*inv(i)%mod; L[0]=0; } void poly_inv(ll *L1,ll *L2,int N,int lg){ int i,len,j; L2[0]=1; for(i=0,len=1;i<=lg;++i,len<<=1){ for(j=0;j<(len<<1);++j) C[j]=j<len?L1[j]:0; NTT(C,len<<1,1,i+1);NTT(L2,len<<1,1,i+1); for(j=0;j<(len<<1);++j) L2[j]=(mod+2-L2[j]*C[j]%mod)%mod*L2[j]%mod; NTT(L2,len<<1,-1,i+1); for(j=0;j<len;++j) L2[j]=L2[j]*inv(len<<1)%mod; for(j=len;j<(len<<1);++j) L2[j]=0; } for(i=N;i<(1<<lg);++i) L2[i]=0; } void poly_sqrt(ll *L1,ll *L2,int N,int lg){ int d,t,i; L2[0]=discrete_sqrt::sqr(L1[0]); for(t=0,d=1;d<=N;++t,d<<=1){ for(i=0;i<(d<<1);++i) Q[i]=i<d?L1[i]:0; for(i=0;i<(d<<1);++i) iB[i]=0; poly_inv(L2,iB,d,t); NTT(Q,d<<1,t+1,1);NTT(L2,d<<1,t+1,1);NTT(iB,d<<1,t+1,1); for(i=0;i<(d<<1);++i) L2[i]=(C[i]*iB[i]%mod+L2[i])%mod*inv(2)%mod; NTT(L2,d<<1,t+1,-1); for(i=0;i<(d<<1);++i) L2[i]=L2[i]*inv(d<<1)%mod; for(i=d;i<(d<<1);++i) L2[i]=0; } } void poly_ln(ll *L1,ll *L2,int N,int lg){ int i; for(i=0;i<(N<<1);++i) D[i]=i<N?L1[i]:0; poly_diff(D,N); for(i=0;i<(N<<1);++i) L2[i]=0; poly_inv(L1,L2,N,lg); NTT(D,N<<1,1,lg+1);NTT(L2,N<<1,1,lg+1); for(i=0;i<(N<<1);++i) L2[i]=L2[i]*D[i]%mod; NTT(L2,N<<1,-1,lg+1); for(i=0;i<(N<<1);++i) L2[i]=L2[i]*inv(N<<1)%mod; poly_int(L2,N); } void poly_exp(ll *L1,ll *L2,int N,int lg){ int i,j,len; L2[0]=1; for(i=0,len=1;i<=lg;++i,len<<=1){ poly_ln(L2,E,len,i); for(j=len;j<(len<<1);++j) E[j]=0; for(j=0;j<(len<<1);++j) C[j]=j<len?L1[j]:0; NTT(L2,len<<1,1,i+1);NTT(E,len<<1,1,i+1);NTT(C,len<<1,1,i+1); for(j=0;j<(len<<1);++j) L2[j]=(1-E[j]+C[j]+mod)%mod*L2[j]%mod; NTT(L2,len<<1,-1,i+1); for(j=0;j<(len<<1);++j) L2[j]=L2[j]*inv(len<<1)%mod; } } void poly_quickpow(ll *L1,ll *L2,int N,int lg,ll k){ int i; poly_ln(L1,P,N,lg); for(i=0;i<N;++i) P[i]=P[i]*k%mod; poly_exp(P,L2,N,lg); } void read(ll &x){ x=0; char c=getchar(); while(c>'9'||c<'0') c=getchar(); while(c>='0'&&c<='9'){ x=(x*10+c-'0')%mod; c=getchar(); } } int main(){ int i,n,m,u; ll k; scanf("%d",&n); read(k); for(m=1,u=0;m<n;m<<=1,++u); for(i=0;i<n;++i) scanf("%lld",&A[i]); poly_quickpow(A,B,m,u,k); for(i=0;i<n;++i) printf("%lld ",B[i]); system("pause"); return 0; }