文件详细信息
本文件的大小为 3520 字节。
//代码常数很大，需要 O2 优化。
#include<cstdio>
#include<cstring>
typedef long long ll;
const ll mod=998244353;
const int N=1000005;
int n;
ll k1,k2;
//$k_1=k \bmod {998244353}$
//$k_2=k \bmod {998244352}$
bool large;
ll a[N],lna[N],b[N],G[N];
int read(){
int ch=getchar(),num=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57)num=(num<<3)+(num<<1)+(ch^48),ch=getchar();
return num;
}
void readk(){
int ch=getchar();
ll num1=0,num2=0;
while(ch<48||ch>57)ch=getchar();
while(ch>=48&&ch<=57){
num1=(num1<<3)+(num1<<1)+(ch^48),num2=((num2<<3)+(num2<<1)+(ch^48))%(mod-1);
if(num1>=mod)num1%=mod,large=true;
ch=getchar();
}
k1=num1,k2=num2;
}
void write(int a){
if(a>=10)write(a/10);
putchar(a%10|48);
}
ll qpow(ll a,int x=mod-2){
if(x==0)return 1%mod;
ll answer=1;
while(x){
if(x&1)answer=answer*a%mod;
a=a*a%mod;
x>>=1;
}
return answer;
}
void swap(ll&a,ll&b){
ll temp=a;
a=b;
b=temp;
}
int rev[N];
const ll invG=qpow(3),inv2=qpow(2);
void NTT(ll*f,int type,int n){
for(int i=0;i<n;i++)
if(i<rev[i])
swap(f[i],f[rev[i]]);
for(int p=2;p<=n;p<<=1){
int len=p>>1;
ll tG=qpow(type==1?3:invG,(mod-1)/p);
for(int k=0;k<n;k+=p){
ll buf=1;
for(int l=k;l<k+len;l++){
ll temp=buf*f[l+len]%mod;
f[l+len]=((f[l]-temp)%mod+mod)%mod;
f[l]=((f[l]+temp)%mod+mod)%mod;
buf=buf*tG%mod;
}
}
}
if(type==0){
ll invn=qpow(n,mod-2);
for(int i=0;i<n;i++)f[i]=f[i]*invn%mod;
}
}
ll A[N],B[N];
void poly_inv(ll*a,ll*b,int n){
b[0]=qpow(a[0],mod-2);
int len,limit;
memset(A,0,sizeof(A));
memset(B,0,sizeof(B));
for(len=1;len<(n<<1);len<<=1){
limit=len<<1;
for(int i=0;i<len;i++)A[i]=a[i],B[i]=b[i];
for(int i=0;i<limit;i++)rev[i]=(rev[i>>1]>>1)|((i&1)?len:0);
NTT(A,1,limit);NTT(B,1,limit);
for(int i=0;i<limit;i++)b[i]=((2ll-A[i]*B[i]%mod)*B[i]%mod+mod)%mod;
NTT(b,0,limit);
for(int i=len;i<limit;i++)b[i]=0;
}
for(int i=n;i<len;i++)b[i]=0;
}
void derivation(ll*a,ll*b,int n){
for(int i=1;i<n;i++)b[i-1]=i*a[i]%mod;
b[n-1]=0;
}
void integral(ll*a,ll*b,int n){
for(int i=1;i<n;i++)b[i]=a[i-1]*qpow(i,mod-2)%mod;
b[0]=0;
}
ll c[N];
void poly_ln(ll*a,ll*b,int n){
derivation(a,c,n),poly_inv(a,b,n);
int lim,l=-1;
for(lim=1;lim<(n<<1);lim<<=1)++l;
for(int i=1;i<lim;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<l);
for(int i=n;i<lim;++i)b[i]=c[i]=0;
NTT(c,1,lim),NTT(b,1,lim);
for(int i=0;i<lim;++i)c[i]=b[i]*c[i]%mod;
NTT(c,0,lim);
integral(c,b,n);
for(int i=n;i<lim;++i)b[i]=0;
}
ll lnb[N];
void poly_exp(ll*a,ll*b,int n){
if(n==1){
b[0]=1;
return;
}
poly_exp(a,b,(n+1)>>1);
poly_ln(b,lnb,n);
int m=1;
for(;m<(n<<1);m<<=1);
for(int i=0;i<m;i++)rev[i]=(rev[i>>1]>>1)|((i&1)?(m>>1):0);
for(int i=0;i<n;i++)lnb[i]=(a[i]-lnb[i]+mod)%mod;
for(int i=n;i<m;i++)lnb[i]=b[i]=0;
lnb[0]++;
NTT(lnb,1,m),NTT(b,1,m);
for(int i=0;i<m;i++)b[i]=b[i]*lnb[i]%mod;
NTT(b,0,m);
for(int i=n;i<m;i++)b[i]=0;
}
int main(){
n=read(),readk();
register int i;
for(i=0;i<n;++i)a[i]=read();
int start=0;
ll invstart=1,inv=1;
for(i=0;i<n;i++){
if(a[i]!=0){
start=i;
invstart=qpow(a[i]);
inv=qpow(a[i],k2);
break;
}
if(i==n-1)start=n;
}
if(start*k1>=n||(start&&large)){
for(int i=0;i<n;i++)putchar('0'),putchar(' ');
return 0;
}
n-=start;
for(i=0;i<n;i++)a[i]=a[i+start]*invstart%mod;
poly_ln(a,lna,n);
for(i=0;i<n;++i)lna[i]=lna[i]*(ll)k1%mod;
poly_exp(lna,b,n);
n+=start;
for(i=0;i<start*k1;i++)putchar('0'),putchar(' ');
for(i=start*k1;i<n;++i)write(b[i-start*k1]*inv%mod),putchar(' ');
return 0;
}