分治FFT

题目链接
虽然这是一个卷积的形式，但是却无法直接卷积，真是难受啊
于是考虑分治，对于当前分治区间([l,r])，假设我们已经求出了(f_l,f_{l+1},dots ,f_{mid})
那么对于(xin [mid+1,r]),([l,mid])的贡献就是

[w_x=sum_{i=l}^{mid}f_icdot g_{x-i} ]

于是乎像(cdq)分治那样做就可以了

code:

#include<bits/stdc++.h>
using namespace std;
const int N=4e5+5,G=3,ivG=332748118,mod=998244353;
struct poly
{
	vector<int>v;
	inline int &operator[](int x)
	{
		while(x>=v.size())v.push_back(0);
		return v[x];
	}
	inline void pre(int x,int lim)
	{
		int t=min(lim,(int)v.size());
		for(int i=x;i<t;++i)v[i]=0;
	}
};
namespace Math
{
	inline int add(int x,int y){x+=y;return x>=mod?x-mod:x;}
	inline int dec(int x,int y){x-=y;return x<0?x+mod:x;}
	inline int qpow(int x,int y)
	{
		int ans=1;
		for(;y;y>>=1,x=1ll*x*x%mod)
			(y&1)&&(ans=1ll*ans*x%mod);
		return ans;
	}
}
namespace Basis
{
	int rev[N],wn[N];
	inline void ntt(poly&f,int lim,bool tp)
	{
		for(int i=0;i<lim;++i)if(i<rev[i])swap(f[i],f[rev[i]]);
		for(int mid=1;mid<lim;mid<<=1)
		{
			int len=mid<<1,g=Math::qpow(tp?ivG:G,(mod-1)/len);
			wn[0]=1;for(int i=1;i<mid;++i)wn[i]=1ll*wn[i-1]*g%mod;
			for(int j=0;j<lim;j+=len)
				for(int k=0;k<mid;++k)
				{
					int x=f[j+k],y=1ll*wn[k]*f[j+mid+k]%mod;
					f[j+k]=Math::add(x,y),f[j+mid+k]=Math::dec(x,y);
				}
		}
	}
	inline poly mul(int n,int m,poly f,poly g)
	{
		int lim=1,l=0;while(lim<n+m)lim<<=1,++l;
		for(int i=0;i<lim;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(l-1));
		f.pre(n,lim),g.pre(m,lim);
		ntt(f,lim,0),ntt(g,lim,0);
		for(int i=0;i<lim;++i)f[i]=1ll*f[i]*g[i]%mod;
		ntt(f,lim,1);int iv=Math::qpow(lim,mod-2);
		for(int i=0;i<lim;++i)f[i]=1ll*f[i]*iv%mod;
		return f;
	}
}
poly f,g;
void cdqntt(int l,int r)
{
	if(l==r)return;
	int mid=l+r>>1;cdqntt(l,mid);poly _f;
	for(int i=l;i<=mid;++i)_f[i-l]=f[i];
	_f=Basis::mul(mid-l+1,r-l+1,_f,g);
	for(int i=mid+1;i<=r;++i)f[i]=Math::add(f[i],_f[i-l]);
	cdqntt(mid+1,r);
}
int main()
{
	int n;scanf("%d",&n);
	for(int i=1;i<n;++i)scanf("%d",&g[i]);
	f[0]=1;cdqntt(0,n-1);
	for(int i=0;i<n;++i)printf("%d ",f[i]);
	return 0;
}