多项式 ln 能过板子,static 数组已清空,样例只有最后两个数有错。
在 namespace 最下面。
#include<bits/stdc++.h>
using namespace std;
#define rep(i,s,t,p) for(int i = s;i <= t;i += p)
#define drep(i,s,t,p) for(int i = s;i >= t;i -= p)
#ifdef LOCAL
auto I = freopen("in.in","r",stdin),O = freopen("out.out","w",stdout);
#else
auto I = stdin,O = stdout;
#endif
using ll = long long;using ull = unsigned long long;
using db = double;using ldb = long double;
namespace PolyBasedNTT{
using std::memset;using std::memcpy;using std::swap;using std::reverse;
#define N LEN
const int Mod = 998244353,G = 3,Gi = 332748118;
const int LEN = 4e6 + 10;
int lastnnn = 0,lastlim = 0,initinvn = 0,_to[N],_inv[N];
int qpow(int a,int b,int Mod = Mod){
int res = 1;
for(;b;b >>= 1,a = 1ll*a*a%Mod)
if(b&1) res = 1ll*res*a%Mod;
return res;
}
int invi(int a){return qpow(a,Mod-2,Mod);}
template<class T>
T FMod(const T x){return x >= Mod?x - Mod:x;}
void bfconvolution(int *a,int *b,int lena,int lenb){
static int w[N];
for(int i = 0;i < lena; ++i) for(int j = 0;j < lenb; ++j)
w[i+j] = FMod(w[i+j]+1ll*a[i]*b[j]%Mod);
copy(w,w+lena+lenb,a);
fill(w,w+lena+lenb,0);
}
int _prepare(int n){
if(lastnnn == n) return lastlim;
lastnnn = n;
uint lim = 1,ct = -1;while(lim <= n) lim <<= 1,ct++;
for(int i = 0;i < lim; ++i) _to[i] = (_to[i>>1]>>1)|((i&1)<<ct);
return (lastlim = lim);
}
void mult(int *f,int *g,int len){for(int i = 0;i < len; ++i) f[i] = 1ll*f[i]*g[i]%Mod;}
void clear(int *f,int len,int val = 0){memset(f,val,4*len);}
void cpy(int *f,int *g,int len){memcpy(f,g,4*len);}
void NTT(int *a,int n,bool type = true){
n = _prepare(n);
for(int i = 0;i < n; ++i) if(i < _to[i]) swap(a[i],a[_to[i]]);
for(int mid = 1;mid < n;mid <<= 1){
int W = qpow(type?G:Gi,(Mod-1)/(mid<<1));
for(int Res = mid<<1,j = 0;j < n;j += Res){
int w = 1;
for(int k = 0;k < mid; ++k,w = 1ll*w*W%Mod){
int x = a[j+k],y = 1ll*w*a[j+k+mid]%Mod;
a[j+k] = FMod(x+y);
a[j+k+mid] = FMod(x-y+Mod);
}
}
}
}
void convolution(int *a,int *b,int n,int m){
int len = n + m,llen = invi(_prepare(len)),Len = _prepare(len);
static int sav[N];
clear(sav,len);cpy(sav,b,len);
NTT(a,len);if(a != b) NTT(b,len);
for(int i = 0;i < Len; ++i) a[i] = 1ll*a[i]*b[i]%Mod;
NTT(a,len,false);
for(int i = 0;i < len; ++i) a[i] = 1ll*a[i]*llen%Mod;
fill(a+len,a+Len,0);cpy(b,sav,len);
}
void invp(int *b,int *a,int n){
if(n == 1) return b[0] = invi(a[0]),void();
invp(b,a,(n+1)>>1);
static int c[N];
int emm = 2*n-1,len = _prepare(emm);
cpy(c,a,n);
clear(c+n,len-n+1);
NTT(c,emm);NTT(b,emm);
for(int i = 0;i < len; ++i) b[i] = FMod(2ll-1ll*b[i]*c[i]%Mod+Mod)*b[i]%Mod;
NTT(b,emm,0);int invn = invi(len);
for(int i = 0;i < n; ++i) b[i] = 1ll*b[i]*invn%Mod;
clear(b+n,len-n+1);
}
void invp(int *a,int n){
static int b[N];invp(b,a,n);
cpy(a,b,n+1);
clear(b,lastlim);
}
void sqrtp(int *a,int n){
static int b1[N],b2[N],b3[N];
int m = n + 1;n = 1;while(n <= m) n <<= 1;
b1[0] = 1;
for(int len = 2;len <= n;len <<= 1){
for(int i = 0;i < (len>>1); ++i) b2[i] = b1[i];
for(int i = 0;i < len; ++i) b3[i] = a[i];
invp(b2,len);
convolution(b3,b2,len,len);
for(int i = 0;i < len; ++i) b1[i] = FMod(b1[i]+b3[i])*499122177ll%Mod;
clear(b2,lastlim);clear(b3,lastlim);clear(b1+len,lastlim-len);
}
cpy(a,b1,m);clear(b1,n+n);clear(b2,n+n);clear(b3,n+n);
}
void rev(int *f,int len){reverse(f,f+len);}
void modp(int *f,int *g,int n,int m){
static int q[N],t[N];
int L = n-m+1;
rev(g,m);cpy(q,g,L);rev(g,m);
rev(f,n);cpy(t,f,L);rev(f,n);
invp(q,L);convolution(q,t,L,L);rev(q,L);
fill(q+L,q+lastlim,0);
convolution(g,q,n,n);
for(int i = 0;i < m-1; ++i) g[i] = FMod(f[i]-g[i]+Mod);
cpy(f,q,L);
clear(f+L,n-L);
clear(q,lastlim);clear(t,lastlim);
}
void Diff(int *f,int n){
for(int i = 0;i < n - 1; ++i) f[i] = 1ll*(i+1)*f[i+1]%Mod;
f[n-1] = 0;
}
void Init(int *inv,int n){
if(initinvn >= n) return;
if(initinvn == 0){
inv[1] = 1;
for(int i = 2;i <= n; ++i) inv[i] = 1ll*inv[Mod%i]*(Mod-Mod/i)%Mod;
initinvn = n;
}
else{
for(int i = initinvn + 1;i <= n; ++i) inv[i] = 1ll*inv[Mod%i]*(Mod-Mod/i)%Mod;
initinvn = n;
}
}
void integral(int *f,int n){
Init(_inv,n);
for(int i = n; i; --i) f[i] = 1ll*f[i-1]*_inv[i]%Mod;
f[0] = 0;
}
void ln(int *f,int n){
static int g[N];
cpy(g,f,n);
invp(g,n);
int LL = lastlim;
Diff(f,n);
convolution(f,g,n,n);
integral(f,n-1);
memset(g,0,sizeof g);
clear(g,lastlim);
}
void exp(int *f,int m){
static int s[N],s2[N],res[N];
int n = 1;while(n < m) n <<= 1;
s2[0] = 1;
for(int len = 2;len <= n;len <<= 1){
cpy(s,s2,len>>1);ln(s,len);
for(int i = 0;i < len; ++i) s[i] = FMod(f[i]-s[i]+Mod);
s[0] = FMod(s[0] + 1);
convolution(s2,s,len,len);
}
cpy(f,s2,m);clear(s,n);clear(s2,n);
}
#undef N
}using namespace PolyBasedNTT;
const int N = 4e5 + 10;
int n,a[N];
signed main(){
cin.tie(nullptr)->sync_with_stdio(false);
cin>>n;
for(int i = 0;i < n; ++i) cin>>a[i];
exp(a,n);
for(int i = 0;i < n; ++i) cout<<a[i]<<' ';cout<<'\n';
}