分治 FFT

为啥要叫分治\(fft\)啊，又用不到\(fft……\)

给定长度为\(n-1\)的数组\(g[1],g[2],……,g[n-1]\)，求\(f[1],f[2],……,f[n]\),其中

\[f[i]=\sum\limits_{j=1}^{i}f[j-i]g[j]
\]

边界为\(f[0]=1\)，答案模\(998244353\)

\(2\le n \le 10^5,0\le g[i]< 998244353\)

我们发现这其实是一个关于\(f\)数组的递推式子，但是肯定不能直接递推

考虑每个对\(f[i]\)有贡献的只有\(f[1]\sim f[i-1]\),我们可以用\(cdq\)分治

假设我们求出了\(f[l->mid]\)的答案，想计算对\(f[mid+1->r]\)的贡献

那么对\(t\in [mid+1,r]\)的贡献为 \(val_t=\sum\limits_{i=l}^{mid}f[i]*g[t-i]\)

是一个卷积形式，可以\(ntt\)，得出\(val_t\)后直接加给\(f[t]\)就好了

其实点名是\(cdq\)分治思路就很清晰了吧，不过边界一如既往的恶心我

#include<bits/stdc++.h>

using namespace std;

namespace red{

#define int long long

	inline int read()

	{

		int x=0;char ch,f=1;

		for(ch=getchar();(ch<'0'||ch>'9')&&ch!='-';ch=getchar());

		if(ch=='-') f=0,ch=getchar();

		while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-'0';ch=getchar();}

		return f?x:-x;

	}

	const int N=5e5+10,p=998244353,G=3,gi=332748118;

	int n;

	int g[N],f[N],pos[N];

	int a[N],b[N];

	inline int fast(int x,int k)

	{

		int ret=1;

		while(k)

		{

			if(k&1) ret=ret*x%p;

			x=x*x%p;

			k>>=1;

		}

		return ret;

	}

	inline void ntt(int *a,int inv,int limit)

	{

		for(int i=0;i<limit;++i)

			if(i<pos[i]) swap(a[i],a[pos[i]]);

		for(int mid=1;mid<limit;mid<<=1)

		{

			int Wn=fast(inv?G:gi,(p-1)/(mid<<1));

			for(int r=mid<<1,j=0;j<limit;j+=r)

			{

				int w=1;

				for(int k=0;k<mid;++k,w=w*Wn%p)

				{

					int x=a[j+k],y=w*a[j+k+mid]%p;

					a[j+k]=x+y;

					if(a[j+k]>=p) a[j+k]-=p;

					a[j+k+mid]=x-y;

					if(a[j+k+mid]<0) a[j+k+mid]+=p;

				}

			}

		}

		if(inv) return;

		inv=fast(limit,p-2);

		for(int i=0;i<limit;++i) a[i]=a[i]*inv%p;

	}

	inline void cdq(int l,int r)

	{

		if(l==r) return;

		int mid=(l+r)>>1;

		cdq(l,mid);

		int limit=1,len=0;

		while(limit<=(mid-l+1)*2) limit<<=1,++len;

		for(int i=0;i<limit;++i) pos[i]=(pos[i>>1]>>1)|((i&1)<<(len-1));

		for(int i=0;i<limit;++i) a[i]=b[i]=0;

		for(int i=l;i<=mid;++i) a[i-l]=f[i];

		for(int i=1;i<=r-l+1;++i) b[i-1]=g[i];

		ntt(a,1,limit);ntt(b,1,limit);

		for(int i=0;i<limit;++i) a[i]=a[i]*b[i]%p;

		ntt(a,0,limit);

		for(int i=mid+1;i<=r;++i) (f[i]+=a[i-l-1])%=p;

		cdq(mid+1,r);

	}

	inline void main()

	{

		n=read();

		f[0]=1;

		for(int i=1;i<n;++i) g[i]=read();

		cdq(0,n-1);

		for(int i=0;i<n;++i) printf("%lld ",f[i]);

	}

}

signed main()

{

	red::main();

	return 0;

}

巴特西

分治 FFT

最新文章

热门文章