多项式分治与傅里叶变换

观前提醒

本文设有大量 ，请确保在所有数学公式渲染完毕之后再阅读，否则会影响阅读体验。

分治与快速变换

分治 是一种基于 分治实现的多项式算法，用于解决一些非常规性的多项式卷积问题，例如：

题目简介

题目名称：分治

题目来源：

评测链接：https://www.luogu.com.cn/problem/P4721

形式化题意：给定一个长度为 的序列 ，并给定一个函数 定义为：

求 ，对 取模。

数据范围：

我们可以考虑递推公式的组成：

$$\begin{align} f(0)&=\nonumber1 \\ f(1)&=\nonumber f(0)\ast g(1) \\ f(2)&=\nonumber f(0)\ast g(2)+f(1)\ast g(1) \end{align}$$

容易发现， 的递推是一个卷积的形式，不同情况在于， 所需要的卷积多项式的其中一个是自己本身，而 会基于所有的 来计算，暴力时间复杂度为 。

对于这种前面的答案会对后面的答案产生贡献的做法，我们可以考虑一种分治的思想。

---

分治实现

关于分治

扯点闲话。

所谓分治，实则分而治之（），类似于 ，将一个难以解决的大问题切分成若干的可以快速解决的小问题，就好比我们在生活中要写一篇有文采的作文，这较为困难，但我们可以先写上一个有吸引力的开头，再写上一个有深度的情节，最后添上一个有情感的结尾，这便是一篇有文采作文。

但你也发现了，如果开头，结尾，内容两两无关的话，这就不能算是一篇作文，更不用提有文采了。所以，分治的难点也不仅仅在于如何“分”，更在如何“治”，你要会分，你也要会如何组装。就像你要会求导，那也就要会积分。

常见的分治有 分治，二分法，三分法，以及多项式分治。

如果我们当前需要求 的值，有 ，我们先进行递归求出 的值，并添加其贡献至 。

我们考虑如何添加其贡献，设区间 对 的贡献为 ，则有：

$$\nonumber w(x)=\sum_{i=l}^{mid}f(i)\ast g(x-i)$$

显然，这个 的限制并不能帮助我们进行多项式卷积，所以我们考虑扩大值域，设 ，得到：

$$w(x)=\sum_{i=l}^{x-1}f(i)\ast g(x-i) \nonumber$$

为了让这个式子更适合我们的多项式卷积，我们让 从 开始枚举，得到：

$$w(x)=\sum_{i=0}^{x-l-1}f(i+l)\ast g(x-i-l) \nonumber$$

我们把其下标进行一定的修改，设定 ，得到：

$$\nonumber w(x)=\sum_{i=0}^{x-l-1}f_1(i)\ast g_1(x-l-1-i)$$

并替换 得到：

$$w(x)=\sum_{i=0}^{n}f_1(i)\ast g_1(n-i) \nonumber$$

这样的话， 就是一个多项式卷积了，就可以使用 快速计算了。根据分治的常规分析法，我们可以知道，这样做的时间复杂度为 。

这道题当然也可以使用多项式求逆来解决，其时间复杂度为 ，较分治而言更为优秀，但我们今天并不会提及。

AC Code

// ----- Eternally question-----
// Problem: P4721 【模板】分治 FFT
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P4721
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// Written by: Eternity
// Time: 2023-01-12 17:04:50
// ----- Endless solution-------

#include<bits/stdc++.h>
#define re register
typedef long long ll;
template<class T>
inline void read(T &x)
{
	x=0;
	char ch=getchar(),t=0;
	while(ch<'0'||ch>'9') t|=ch=='-',ch=getchar();
	while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
	if(t) x=-x;
}
template<class T,class ...T1>
inline void read(T &x,T1 &...x1){ read(x),read(x1...); }
template<class T>
inline void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
template<>
inline void write(bool x){ putchar(x?'1':'0'); }
template<>
inline void write(char c){ putchar(c); }
template<>
inline void write(char *s){ while(*s!='\0') putchar(*s++); }
template<>
inline void write(const char *s){ while(*s!='\0') putchar(*s++); }
template<class T,class ...T1>
inline void write(T x,T1 ...x1){ write(x),write(x1...); }
template<class T>
inline bool checkMax(T &x,T y){ return x<y?x=y,1:0; }
template<class T>
inline bool checkMin(T &x,T y){ return x>y?x=y,1:0; }
const int MAXN=2e5+10;
const int P=998244353,G=3,invG=332748118;
int N;
ll f[MAXN],g[MAXN];
inline ll qPow(ll a,ll b)
{
	ll res=1;
	while(b)
	{
		if(b&1) res=res*a%P;
		a=a*a%P;b>>=1;
	}
	return res;
}
int Tot,Bit,Rev[MAXN];
inline void NTT(ll a[],int n,int inv)
{
	for(int i=0;i<n;++i)
		if(i<Rev[i]) std::swap(a[i],a[Rev[i]]);
	for(int mid=1;mid<n;mid<<=1)
	{
		ll w1=qPow(inv==1?G:invG,(P-1)/(mid<<1));
		for(int i=0;i<n;i+=mid*2)
		{
			ll wk=1;
			for(int j=0;j<mid;++j,wk=wk*w1%P)
			{
				ll x=a[i+j],y=a[i+j+mid]*wk%P;
				a[i+j]=(x+y)%P,a[i+j+mid]=(x-y+P)%P;
			}
		}
	}
	if(inv==-1)
	{
		ll iv=qPow(n,P-2);
		for(int i=0;i<n;++i) a[i]=a[i]*iv%P;
	}
}
inline void Mul(ll a[],ll b[],int n,int bit)
{
	for(int i=0;i<n;++i) Rev[i]=(Rev[i>>1]>>1)|((i&1)<<(bit-1));
	NTT(a,n,1),NTT(b,n,1);
	for(int i=0;i<n;++i) a[i]=a[i]*b[i]%P;
	NTT(a,n,-1);
}
ll a[MAXN],b[MAXN];
void Divide(ll f[],ll g[],int l,int r)
{
	if(l==r) return ;
	int mid=(l+r)>>1,len=r-l+1,bit=0,tot;
	Divide(f,g,l,mid);
	while((1<<bit)<=len) ++bit;
	tot=1<<bit;
	std::memset(a,0,tot*sizeof(ll));
	std::memset(b,0,tot*sizeof(ll));
	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];
	Mul(a,b,tot,bit);
	for(int i=mid+1;i<=r;++i) f[i]=(f[i]+a[i-l-1])%P;
	Divide(f,g,mid+1,r);
}
signed main()
{
	// freopen(".in","r",stdin);
	// freopen(".out","w",stdout);
	read(N),f[0]=1;
	for(int i=1;i<N;++i) read(g[i]);
	Divide(f,g,0,N-1);
	for(int i=0;i<N;++i) write(f[i],' ');
	return 0;
}
/*

*/

---

例题

待补充，还没有找到能用分治 做的题。

准确说是找到了，但是不会做，毕竟 *3200 。