分治FFT/NTT
阅读原文时间:2023年07月08日阅读:3

粘板子:

#include
#include
#include
using namespace std;
typedef long long ll;
const int MOD = 998244353;
const int N = 100050;
const int M = N*3;
template
inline void read(T&x)
{
T f = 1,c = 0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} x = f*c; } templateinline void Mod(T&x){if(x>=MOD)x-=MOD;}
int fastpow(int x,int y)
{
int ret = 1;
while(y)
{
if(y&1)ret=1ll*ret*x%MOD;
x=1ll*x*x%MOD;y>>=1;
}
return ret;
}
int inv(int x){return fastpow(x,MOD-2);}
int to[M],lim,L,LL[M];
void init(int len)
{
lim=LL[2]=1;
while(lim>1]>>1)|((i&1)<<(L-1))); } void ntt(int*a,int len,int k) { for(int i=0;i>1;i++)swap(a[i],a[len-i]);
int Inv = inv(len);
for(int i=0;i>1;
cdq(l,mid);
get_lim(2*(r-l+1));
for(int i=0;i<lim;i++)a[i]=b[i]=0;
for(int i=0;i<=mid-l;i++)a[i]=f[l+i];
for(int i=1;i<=r-l+1;i++)b[i]=g[i];
ntt(a,lim,1),ntt(b,lim,1);
for(int i=0;i<=lim;i++)c[i]=1ll*a[i]*b[i]%MOD;
ntt(c,lim,-1);
for(int i=mid+1-l;i<=r-l;i++)Mod(f[i+l]+=c[i]);
cdq(mid+1,r);
}
int main()
{
// freopen("tt.in","r",stdin);
read(n);init(n<<1);f[0]=1;
for(int i=1;i<n;i++)read(g[i]);
cdq(0,lim-1);
for(int i=0;i<n;i++)printf("%d ",f[i]);
puts("");
return 0;
}

手机扫一扫

移动阅读更方便

阿里云服务器
腾讯云服务器
七牛云服务器

你可能感兴趣的文章