description

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

\[f[i]=\sum_{j=1}^if[i-j]g[j]
\]

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

analysis

一道分治\(NTT\)板题
经历过城市规划那题的洗礼之后这题变得微不足道
考虑\(CDQ\)分治，求出\([l,mid]\)对\([mid+r]\)的贡献
把\(f[l,mid]\)拉出来，与\(g[1..r-l]\)相乘，答案数组的后\(r-mid\)位就是分别对\([mid+r]\)的贡献
具体可以画出两个多项式在分治过程中的相乘，结合每一个\(f\)的值就可以弄清楚
由于这个\(NTT\)很清真所以\(l==r\)时就直接\(return\)了，当然也没有各种阶乘逆元什么的
下次学多项式求逆再来做一次这题（FLAG）

code

#pragma GCC optimize("O3")

#pragma G++ optimize("O3")

#include<stdio.h>

#include<string.h>

#include<algorithm>

#define MAXN 400005

#define G 3

#define mod 998244353

#define ll long long

#define reg register ll

#define fo(i,a,b) for (reg i=a;i<=b;++i)

#define fd(i,a,b) for (reg i=a;i>=b;--i)

using namespace std;

ll f[MAXN],g[MAXN];

ll a[MAXN],b[MAXN],rev[MAXN];

ll n,m;

inline ll read()

{

	ll x=0,f=1;char ch=getchar();

	while (ch<'0' || '9'<ch){if (ch=='-')f=-1;ch=getchar();}

	while ('0'<=ch && ch<='9')x=x*10+ch-'0',ch=getchar();

	return x*f;

}

inline ll work(ll x)

{

	ll y=1;

	while (y<x)y<<=1;

	return y<<1;

}

inline ll pow(ll x,ll y)

{

	ll z=1;

	while (y)

	{

		if (y&1)z=z*x%mod;

		x=x*x%mod,y>>=1;

	}

	return z;

}

inline void ntt(ll a[],ll len,ll inv)

{

	ll bit=0;

	while ((1<<bit)<len)++bit;

	fo(i,0,len-1)

	{

		rev[i]=(rev[i>>1]>>1)|((i&1)<<(bit-1));

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

	}

	for (ll mid=1;mid<len;mid*=2)

	{

		ll tmp=pow(G,(mod-1)/(mid*2));

		if (inv==-1)tmp=pow(tmp,mod-2);

		for (ll i=0;i<len;i+=mid*2)

		{

			ll omega=1;

			for (ll j=0;j<mid;++j,omega=omega*tmp%mod)

			{

				ll x=a[i+j],y=omega*a[i+j+mid]%mod;

				a[i+j]=(x+y)%mod,a[i+j+mid]=(x-y+mod)%mod;

			}

		}

	}

}

inline void CDQ(ll l,ll r)

{

	if (l==r)return;

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

	CDQ(l,mid);

	ll len=work(r-l+1),invv=pow(len,mod-2);

	fo(i,0,len-1)a[i]=b[i]=0;

	fo(i,1,mid-l+1)a[i]=f[l+i-1];

	fo(i,1,r-l)b[i]=g[i];

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

	fo(i,0,len-1)a[i]=(a[i]*b[i]%mod);

	ntt(a,len,-1);

	fo(i,0,len-1)a[i]=(a[i]*invv)%mod;

	fo(i,mid+1,r)(f[i]+=a[i-l+1])%=mod;

	CDQ(mid+1,r);

}

int main()

{

	freopen("CDQNTT.in","r",stdin);

	n=read(),m=work(n);

	fo(i,1,n-1)g[i]=read();

	f[1]=1,CDQ(1,m/2);

	fo(i,1,n)printf("%lld ",f[i]);

	printf("\n");

	return 0;

}

巴特西

【luoguP4721】分治 FFT

description

analysis

code

最新文章

热门文章