```cpp
#include<bits/stdc++.h>
#define rd(x) x=read()
#define ll long long
#define ri register int
#define ull unsigned long long
#define int long long
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
using namespace std;
const int mod=998244353;
const int N=2e6+5;
const int g=3;
inline int read(){int x=0,f=1;char ch=getchar();while((ch>'9' || ch<'0')){if(ch=='-') f=-1;ch=getchar();}while('0'<=ch && ch<='9') x=x*10+(ch^48),ch=getchar();return x*f;}
inline ll ksm(ll x,int y=mod-2,int z=mod){ll ret=1;while (y){if (y&1) ret=ret*x%mod;x=x*x%mod;y>>=1;}return ret;}
const int invg=ksm(g);
int invn;
int S[N<<1];
int inv[N];
int tr[N<<1],tf;
void Init(int n){inv[1]=1;for (ri i=2;i<=n;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;}
void print(int *f,int n){for (ri i=0;i<n;i++) printf("%lld ",f[i]);puts("");}
void XC(int *f,int *G,int n){for (ri i=0;i<n;i++) f[i]=1ll*f[i]*G[i]%mod;}
void init(int n)
{
if (tf==n) return;tf=n;
for (ri i=0;i<n;i++) tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
}
void NTT(int *G,bool flag,int n)
{
init(n);
static ull f[N<<1],W[N<<1];
W[0]=1;
for (ri i=0;i<n;i++) f[i]=(((ll)mod<<5)+G[tr[i]])%mod;
for (ri l=1;l<n;l<<=1)
{
int tG=ksm(flag?g:invg,(mod-1)/(l<<1));
for (ri i=1;i<l;i++) W[i]=W[i-1]*tG%mod;
for (ri k=0;k<n;k+=(l<<1))
{
for (ri p=0;p<l;p++)
{
int tt=W[p]*f[k|l|p]%mod;
f[k|l|p]=f[k|p]+mod-tt;
f[k|p]+=tt;
}
}
if (l==(1<<10)) for (ri i=0;i<n;i++) f[i]%=mod;
}
if (flag==0) {int invn=ksm(n);for (ri i=0;i<n;i++) G[i]=f[i]%mod*invn%mod;}
else for (ri i=0;i<n;i++) G[i]=f[i]%mod;
}
void times(int *f,int *G,int len,int lim)
{
int n=1;for (n;n<len+len;n<<=1);
cpy(S,G,n);
for (ri i=len;i<n;i++) S[i]=0;
NTT(f,1,n);NTT(S,1,n);XC(f,S,n);NTT(f,0,n);
for (ri i=lim;i<n;i++) f[i]=0;
clr(S,n);
}
int F[N<<1],G[N<<1];
int A[N<<1],B[N<<1];
void solve(int l,int r)
{
if (l==r) return;
int len=r-l+1;
int mid=(l+r)>>1;
solve(l,mid);
int lim=1;
while (lim<len) lim<<=1;
clr(A,lim+1);clr(B,lim+1);
for (int i=l;i<=mid;i++) A[i-l]=F[i];
for (int i=1;i<=r-l;i++) B[i-1]=G[i];
times(A,B,lim,lim);
for (int i=mid+1;i<=r;i++) F[i]=(F[i]+A[i-l-1])%mod;
solve(mid+1,r);
}
int n;
signed main()
{
rd(n);F[0]=1;
for (ri i=1;i<n;i++) rd(G[i]);
solve(0,n-1);
print(F,n);
}
```
宏定义部分由于懒所以比较诡异,但应该不影响运行
by AsunderSquall @ 2020-12-26 10:29:52
多项式求逆 yyds!
by dead_X @ 2020-12-26 10:31:06
@[我知道了王子](/user/70132) 中间没清空 调好了
```cpp
#include<bits/stdc++.h>
#define rd(x) x=read()
#define ll long long
#define ri register int
#define ull unsigned long long
#define int long long
#define clr(f,n) memset(f,0,sizeof(int)*(n))
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*(n))
using namespace std;
const int mod=998244353;
const int N=2e6+5;
const int g=3;
inline int read(){int x=0,f=1;char ch=getchar();while((ch>'9' || ch<'0')){if(ch=='-') f=-1;ch=getchar();}while('0'<=ch && ch<='9') x=x*10+(ch^48),ch=getchar();return x*f;}
inline ll ksm(ll x,int y=mod-2,int z=mod){ll ret=1;while (y){if (y&1) ret=ret*x%mod;x=x*x%mod;y>>=1;}return ret;}
const int invg=ksm(g);
int invn;
int S[N<<1];
int inv[N];
int tr[N<<1],tf;
void Init(int n){inv[1]=1;for (ri i=2;i<=n;i++)inv[i]=1ll*inv[mod%i]*(mod-mod/i)%mod;}
void print(int *f,int n){for (ri i=0;i<n;i++) printf("%lld ",f[i]);puts("");}
void XC(int *f,int *G,int n){for (ri i=0;i<n;i++) f[i]=1ll*f[i]*G[i]%mod;}
void init(int n)
{
if (tf==n) return;tf=n;
for (ri i=0;i<n;i++) tr[i]=(tr[i>>1]>>1)|((i&1)?n>>1:0);
}
void NTT(int *G,bool flag,int n)
{
init(n);
static ull f[N<<1],W[N<<1];
W[0]=1;
for (ri i=0;i<n;i++) f[i]=(((ll)mod<<5)+G[tr[i]])%mod;
for (ri l=1;l<n;l<<=1)
{
int tG=ksm(flag?g:invg,(mod-1)/(l<<1));
for (ri i=1;i<l;i++) W[i]=W[i-1]*tG%mod;
for (ri k=0;k<n;k+=(l<<1))
{
for (ri p=0;p<l;p++)
{
int tt=W[p]*f[k|l|p]%mod;
f[k|l|p]=f[k|p]+mod-tt;
f[k|p]+=tt;
}
}
if (l==(1<<10)) for (ri i=0;i<n;i++) f[i]%=mod;
}
if (flag==0) {int invn=ksm(n);for (ri i=0;i<n;i++) G[i]=f[i]%mod*invn%mod;}
else for (ri i=0;i<n;i++) G[i]=f[i]%mod;
}
void times(int *f,int *G,int len,int lim)
{
int n=1;for (n;n<len+len;n<<=1);
cpy(S,G,n);
for (ri i=len;i<n;i++) S[i]=0;
NTT(f,1,n);NTT(S,1,n);XC(f,S,n);NTT(f,0,n);
for (ri i=lim;i<n;i++) f[i]=0;
clr(S,n);
}
int F[N<<1],G[N<<1];
int A[N<<1],B[N<<1];
void solve(int l,int r)
{
if (l==r) return;
int len=r-l+1;
int mid=(l+r)>>1;
solve(l,mid);
int lim=1;
while (lim<len + len) lim<<=1;
clr(A,lim+1);clr(B,lim+1);
for (int i=l;i<=mid;i++) A[i-l]=F[i];
for (int i=1;i<=r-l;i++) B[i-1]=G[i];
times(A,B,len,len);
for (int i=mid+1;i<=r;i++) F[i]=(F[i]+A[i-l-1])%mod;
solve(mid+1,r);
}
int n;
signed main()
{
rd(n);F[0]=1;
for (ri i=1;i<n;i++) rd(G[i]);
solve(0,n-1);
print(F,n);
}
```
by dead_X @ 2020-12-26 10:37:31
Orz thx
by AsunderSquall @ 2020-12-26 10:38:55