尝试对拍无果,只好来找万能的谷民求助。
思路就是先 ln 再 exp 。
代码如下:
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define ch() getchar()
#define pc(x) putchar(x)
using namespace std;
template<typename T>void read(T&x){
char c;int f;
for(c=ch(),f=1;c<'0'||c>'9';c=ch())if(c=='-')f=-f;
for(x=0;c>='0'&&c<='9';c=ch())x=x*10+(c&15);x*=f;
}
template<typename T>void write(T x){
static char q[64];int cnt=0;
if(x==0)return pc('0'),void();
if(x<0)pc('-'),x=-x;
while(x)q[cnt++]=x%10,x/=10;
while(cnt--)pc(q[cnt]+'0');
}
const int maxn=800005,mod=998244353,g_=3;
int mo(const int x){
return x>=mod?x-mod:x;
}
int power(int a,int x){
int re=1;
while(x){
if(x&1)re=1ll*re*a%mod;
a=1ll*a*a%mod,x>>=1;
}
return re;
}
int rev[maxn];
void initNTT(int m,int&n){
n=1;int cn=-1;
while(n<m)n<<=1,++cn;
for(int i=1;i<n;++i)
rev[i]=(rev[i>>1]>>1)|((i&1)<<cn);
}
void NTT(int*F,int n,int rv){
for(int i=0;i<n;++i)if(rev[i]<i)
F[i]^=F[rev[i]]^=F[i]^=F[rev[i]];
for(int mid=1;mid<n;mid<<=1){
const int len=mid<<1,gn=power(g_,(mod-1)/len);
for(int i=0;i<n;i+=len){
for(int j=0,g=1;j<mid;++j,g=1ll*g*gn%mod){
int l=i+j,r=l+mid;
int L=F[l],R=1ll*F[r]*g%mod;
F[l]=mo(L+R),F[r]=mo(mod-R+L);
}
}
}
if(!rv)return;reverse(F+1,F+n);int I=power(n,mod-2);
for(int i=0;i<n;++i)F[i]=1ll*F[i]*I%mod;
}
int Inv[maxn];
void inv(int*F,int*G,int n){
//G(x)=inv(F(x)) mod x^n;
if(n==1)return G[0]=power(F[0],mod-2),void();
inv(F,G,(n+1)>>1);for(int i=(n+1)>>1;i<n;++i)G[i]=0;
int cp=n;initNTT((n+1)*2,n);
for(int i=0;i<cp;++i)Inv[i]=F[i];for(int i=cp;i<n;++i)Inv[i]=G[i]=0;
NTT(Inv,n,0);NTT(G,n,0);for(int i=0;i<n;++i)
G[i]=1ll*G[i]*mo(mod-1ll*G[i]*Inv[i]%mod+2)%mod;
NTT(G,n,1);for(int i=cp;i<n;++i)G[i]=0;
}
int Ln[maxn];
void ln(int*F,int*G,int n){
//G(x)=ln(F(x)) mod x^n;
for(int i=0;i<n;++i)Ln[i]=0;
inv(F,Ln,n);int cp=n;
initNTT((n+1)*2,n);
for(int i=0;i<cp;++i)G[i]=1ll*F[i+1]*(i+1)%mod;
for(int i=cp;i<n;++i)G[i]=Ln[i]=0;NTT(G,n,0);NTT(Ln,n,0);
for(int i=0;i<n;++i)G[i]=1ll*G[i]*Ln[i]%mod;NTT(G,n,1);
for(int i=cp-1;i>=1;--i)G[i]=1ll*G[i-1]*power(i,mod-2)%mod;
G[0]=0;for(int i=cp;i<n;++i)G[i]=0;
}
int Exp[maxn];
void exp(int*F,int*G,int n){
//G(x)=exp(F(x)) mod x^n;
if(n==1)return G[0]=1,void();exp(F,G,(n+1)>>1);
for(int i=(n+1)>>1;i<n;++i)G[i]=0;
for(int i=0;i<n;++i)Exp[i]=0;ln(G,Exp,n);
for(int i=0;i<n;++i)Exp[i]=mo(mod-Exp[i]+F[i]+(i==0));
int cp=n;initNTT((n+1)*2,n);
for(int i=cp;i<n;++i)Exp[i]=G[i]=0;NTT(G,n,0);NTT(Exp,n,0);
for(int i=0;i<n;++i)G[i]=1ll*G[i]*Exp[i]%mod;
NTT(G,n,1);for(int i=cp;i<n;++i)G[i]=0;
}
int Power[maxn];
void power(int*F,int*G,int n,int m0,int m1,int m2){
//G(x)=power(F(x),m) mod x^n;
//m0=m%mod m1=m%(mod-1) m2=stand for m
if(m0==0){for(int i=0;i<n;++i)G[i]=(i==0);return;}
int no=0;while(no<n&&F[no]==0)++no;
if(1ll*no*m2>=n){for(int i=0;i<n;++i)G[i]=0;return;}
int V=F[no],I=power(V,mod-2);
for(int i=0;i+no<n;++i)G[i]=1ll*F[i+no]*I%mod,Power[i]=0;
for(int i=n-no;i<n;++i)G[i]=Power[i]=0;ln(G,Power,n);
for(int i=0;i<n;++i)Power[i]=1ll*Power[i]*m0%mod;
exp(Power,G,n);V=power(V,m1);no*=m2;
for(int i=n-1;i>=no;--i)G[i]=1ll*G[i-no]*V%mod;
for(int i=no-1;i>=0;--i)G[i]=0;
}
int A[maxn],B[maxn];
int main(){
int n,m=0,m_=0,m__=0;read(n);
char c=ch();
for(;c<'0'||c>'9';c=ch());
for(;c>='0'&&c<='9';c=ch()){
m=mo(1ll*m*10%mod+(c&15)),
m_=(1ll*m_*10%(mod-1)+(c&15))%(mod-1);
if(m__<=n)m__=m__*10+(c&15);
}
for(int i=0;i<n;++i)read(A[i]);
power(A,B,n,m,m_,m__);
for(int i=0;i<n;++i)write(B[i]),pc(" \n"[i==n-1]);
return 0;
}
/*
所以,永远不要问丧钟为谁而鸣,它为你而鸣。
*/