LG4721 【模板】分治 FFT

P4721 【模板】分治 FFT

题目背景

也可用多项式求逆解决。

题目描述

给定长度为 $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$ 。

输入输出格式

输入格式:

第一行一个正整数 $n$ 。

第二行共 $n-1$ 个非负整数 $g[1],g[2],..,g[n-1]$,用空格隔开。

输出格式:

一行共 $n$ 个非负整数,表示 $f[0],f[1],..,f[n-1]$ 模 $998244353$ 的值。

输入输出样例

输入样例#1: 复制
4
3 1 2
输出样例#1: 复制
1 3 10 35
输入样例#2: 复制
10
2 456 32 13524543 998244352 0 1231 634544 51
输出样例#2: 复制
1 2 460 1864 13738095 55389979 617768468 234028967 673827961 708520894

说明

$2leq nleq 10^5$

$0leq g[i]<998244353$

(g[0]=0)这应该是具体的题目推出来的通性,否则自己就可以反复更新自己了。

Great_Influence的分治FFT

发现题目的要求类似于卷积,于是考虑使用FFT。但是后面的数字基于前面的数字,无法快速计算,时间复杂度退化至(O(n^2))。于是我们考虑将类似的转移同时进行,来节省复杂度。

考虑利用分治。

假设我们求出了(l o mid)的答案,要求这些点对(mid+1 o r)的影响,那么对右半边点(f[x])的贡献为:

[f[x]=sum_{i=l}^{mid} f[i] * g[x-i] ]

这部分可以利用卷积来快速计算。计算完以后,答案直接加到答案数组就可以了。

需要注意的是,如果要求左边点对右边点的影响,首先整个区间以左对该区间的贡献应该先求出。所以分治过程为先分治左边,再求出中间,最后递归右边。

时间复杂度(O(nlog^2n))

有一个卡常技巧,就是可以发现你计算的时候只会用到 (md-lsim r-l) 的这一部分,前半部分不需要管。因此,直接用循环卷积对它进行处理,做乘法的时候不必做长度为 (1.5(r-l+1)) 的,只需要做长度为 (r-l+1) 的就可以了。

所谓循环卷积呢,就是FFT溢出的值会从(0)开始填上。实际卷出(1.5(r-l+1)),超出部分填到了前(0.5(r-l+1)),而我们需要的值是中间一段,所以不影响。

void num_trans(polynomial&a,int inverse){
    int limit=a.size(),len=log2(limit);
    static vector<int> bit_rev;
    if(bit_rev.size()!=limit){
        bit_rev.resize(limit);
        for(int i=0;i<limit;++i) bit_rev[i]=bit_rev[i>>1]>>1|(i&1)<<(len-1);
    }
    for(int i=0;i<limit;++i)if(i<bit_rev[i]) swap(a[i],a[bit_rev[i]]);
    for(int step=1;step<limit;step<<=1){
        int gn=fpow(inverse==1?g:g_inv,(mod-1)/(step<<1));
        for(int even=0;even<limit;even+=step<<1){
            int odd=even+step,gk=1;
            for(int k=0;k<step;++k,gk=mul(gk,gn)){
                int t=mul(gk,a[odd+k]);
                a[odd+k]=add(a[even+k],mod-t),a[even+k]=add(a[even+k],t);
            }
        }
    }
    if(inverse==-1){
        int lim_inv=fpow(limit,mod-2);
        for(int i=0;i<limit;++i) a[i]=mul(a[i],lim_inv);
    }
}
void solve(polynomial&f,polynomial&g,int l,int r){
	if(l==r){
		if(!l) f[l]=1;
		return;
	}
	int mid=(l+r)>>1;
	solve(f,g,l,mid);
	polynomial a(f.begin()+l,f.begin()+mid+1),b(g.begin(),g.begin()+r-l+1); // extract x^l
	int limit=1<<int(ceil(log2(r-l+1)));
	a.resize(limit),num_trans(a,1);
	b.resize(limit),num_trans(b,1);
	for(int i=0;i<limit;++i) a[i]=mul(a[i],b[i]);
	num_trans(a,-1);
	for(int i=mid+1;i<=r;++i) f[i]=add(f[i],a[i-l]);
	solve(f,g,mid+1,r);
}

int main(){
	int n=read<int>();
	polynomial f(n),g(n);
	for(int i=1;i<n;++i) read(g[i]);
	solve(f,g,0,n-1);
	for(int i=0;i<n;++i) printf("%d ",f[i]);
	return 0;
}
原文地址:https://www.cnblogs.com/autoint/p/divided_convolution.html