分治 fft 的一种 nlogn 做法

问题是给定 \(g_{1...n}\), 求 \(f_{0...n}\), 其中 \(f_0=1,f_i=\sum\limits_{j<i}f_jg_{i-j}\).
考虑分治 .
现在要计算 \(f_{0...r}\) , 设 \(mid=\lfloor\frac r2\rfloor\).
假设我们已经计算出 \(f_{0...mid}\).
那么我们先计算 \(f_{0...mid}\)\(f_{mid+1...r}\) 的贡献 , 这里直接乘 \(g\) 即可 .
然后需要计算 \(f_{mid+1...r}\) 对自己的贡献 , 然后发现 \(f_{mid+1...r}\) 对自己贡献的系数就是 \(f_{0...mid}\) . 证明考虑展开 \(f_i\) 表达式 .
那么就让 \(f_{mid+1...r}\) 乘上 \(f_{0...mid}\) 贡献到 \(f_{mid+1...r}\) 即可 .
时间复杂度为 \(T(n)=T(\frac n2)+n\log n=O(n\log n)\)

LuoguP4721code
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
int read()
{
	int ret=0;bool f=0;char c=getchar();
	while(c>'9'||c<'0')f|=(c=='-'),c=getchar();
	while(c>='0'&&c<='9')ret=(ret<<3)+(ret<<1)+(c^48),c=getchar();
	return f?-ret:ret;
}
const int mod=998244353;
int qpow(int a,int b){int ret=1;for(;b;b>>=1,a=(ll)a*a%mod)if(b&1)ret=(ll)ret*a%mod;return ret;}
int R[1<<21],W[1<<21];
int n;
struct poly
{
	vector<int>v;
	int&operator[](const int &i){return v[i];}
	int len(){return v.size();}
	void set(int l){v.resize(l);}
	void ntt(int L,int typ)
	{
		int n=1<<L;
		for(int i=0;i<n;i++)R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
		W[0]=1;W[1]=qpow(3,(mod-1)/n);if(typ==-1)W[1]=qpow(W[1],mod-2);
		for(int i=2;i<n;i++)W[i]=(ll)W[i-1]*W[1]%mod;
		set(n);
		for(int i=0;i<n;i++)if(R[i]>i)swap(v[R[i]],v[i]);
		for(int t=n>>1,d=1;d<n;d<<=1,t>>=1)
			for(int i=0;i<n;i+=(d<<1))
				for(int j=0;j<d;j++)
				{
					int tmp=(ll)W[t*j]*v[i+j+d]%mod;
					v[i+j+d]=(v[i+j]-tmp+mod)%mod;
					v[i+j]=(v[i+j]+tmp)%mod;
				}
		if(typ==-1){int inv=qpow(n,mod-2);for(int i=0;i<n;i++)v[i]=(ll)v[i]*inv%mod;}
	}
	void adjust(){while(len()>1&&v.back()==0)v.pop_back();}
	poly operator *(const poly &x)const
	{
		poly ret,tmp0=*this,tmp1=x;
		int L=ceil(log2(tmp0.len()+tmp1.len())),n=1<<L;
		tmp0.ntt(L,1);tmp1.ntt(L,1);
		ret.set(n);
		for(int i=0;i<n;i++)ret[i]=(ll)tmp0[i]*tmp1[i]%mod;
		ret.ntt(L,-1);ret.adjust();return ret;
	}
}f,g;
void solve(int r)
{
	if(r==0){f[r]=1;return;}
	int mid=r>>1;
	solve(mid);
	poly tmp0,tmp1;
	tmp0.set(mid+1);
	for(int i=0;i<=mid;i++)tmp0[i]=f[i];
	tmp1.set(r+1);
	for(int i=0;i<=r;i++)tmp1[i]=g[i];
	tmp0=tmp0*tmp1;
	for(int i=mid+1;i<=r;i++)f[i]=tmp0[i];
	tmp0.set(mid+1);
	for(int i=0;i<=mid;i++)tmp0[i]=f[i];
	tmp1.set(r+1);
	for(int i=0;i<=mid;i++)tmp1[i]=0;
	for(int i=mid+1;i<=r;i++)tmp1[i]=f[i];
	tmp0=tmp0*tmp1;
	for(int i=mid+1;i<=r;i++)f[i]=tmp0[i];
}
int main()
{
	n=read();
	g.set(n);
	for(int i=1;i<n;i++)g[i]=read();
	f.set(n);
	solve(n-1);
	for(int &i:f.v)printf("%d ",i);putchar('\n');
	return 0;
}

推荐这些文章:

2021牛客暑期多校训练营1 H - Hash Function (套路构造+ fft/ntt加速多项式乘法)

题意:
一个长度为\(n,n\le500000\)的数列,其中的元素\(0\le a_i\le500000\),现在让你找到一个最小的正整数\(x\)使得,\(i\in[1,n],a_i\%x\)的值,全部唯一。
思路:
假如有两个位置\(i < j\),\(a_i \%x = a_j\%x\),即\(|a_i-a_j|\%x=0\),如果我们能确定这个数列所能产生的所有的差值,那么一个合法的\(x\)即代表对于所有的存在的差值来说\(x\)都不是他们的因子。
我们从\(1-n\)枚举\(i\),然后枚举这个数的倍数,如果这个数存在,那么\(i\)即不合法。
过程是一个经典的调和级数的...

多项式工业基础与全家桶

多项式工业基础与全家桶
开坑待填,放个常数巨大的板子先
#define Maxn 200005
#define mod 998244353
inline int ksm(int x,int y=mod-2)
{
int ret=1;
for(;y;y>>=1,x=1ll*x*x%mod) if(y&1) ret=1ll*ret*x%mod;
return ret;
}
const int G=3,invG=ksm(3,mod-2);
int tr[Maxn<<1];
struct Poly
{
int len,f[Maxn<<1];
Po...

多校省选模拟8

多校省选模拟8
体育测试(test)
题意
给你 \(N\) 个人,你要给他们排队,每个人有一个限制,表示自己的位置必须 \(\ge a_i\),或者是 \(\le a_i\)。
问有多少种合法的排队方法。
\(N\le 5000\),答案对于 \(998244353\) 取模。
题解
我们考虑,如果都只有一类限制的话,答案会成啥,比如都是 \(\le a_i\) 的限制。
那么我们只要按照 \(a_i\) 从小到大排序,然后我们的答案自然就是 \(\prod_{i=1}^N(a_i-i+1)\)。
我们考虑,把一个 \(\ge a_i\) 的限制,容斥成为 \(\le n\) 的限制和 \...

2022.03.01 FFT与NNT

2022.03.01 FFT与NNT
https://www.luogu.com.cn/blog/wangrx/solution-p1919
https://www.luogu.com.cn/blog/attack/solution-p38032
P3803 【模板】多项式乘法(FFT)(NTT模板)
https://www.luogu.com.cn/problem/P3803
#include<bits/stdc++.h>
using namespace std;

#define int long long
const int N=3e6+10;
const int mod=...

【luogu P4721】【模板】分治 FFT(NTT)(多项式求逆 / cdq分治)

【模板】分治 FFT
题目链接:luogu P4721
题目大意
给你多项式 \(G\) 满足 \(G_0=0\)。
然后要你求多项式 \(F\) 的前 \(n\) 项满足:\(F_{i}=\sum\limits_{j=1}^iF_{i-j}G_j\)。
思路
cdq分治
你会发现对于一个你要求的范围 \([l,r]\),你如果求出了 \([l,mid]\),你就可以拿他来求它这个部分对 \([mid+1,r]\) 的贡献,然后问题就变成了求 \([mid+1,r]\) 的。
所以就是一个 cdq 分治。
那你考虑这个横跨的部分怎么求。
那你 \(F\) 是 \([l,mid]\),那你 \...

Topcoder 12141 - SweetFruits(矩阵树定理+二项式反演+meet-in-the-middle)

题面传送门
考虑枚举哪些水果是真甜的,设该集合为 \(S\),那么可以发现,当我们固定 \(S\) 时,连边方案数只与 \(S\) 的大小有关,具体来说,设 \(f_x\) 表示在所有甜味值不是 \(-1\) 的水果中有 \(x\) 个是真甜的方案数,那么对于一个具体的 \(S\),满足所有真甜水果的集合恰好是 \(S\) 的生成树个数就是 \(f_{|S|}\)。
首先考虑怎么求 \(f_x\),设 \(m\) 表示甜味值不是 \(-1\) 的水果数量,那么我们考虑先求出 \(g_x\) 表示钦定 \(m-x\) 个水果不是真甜的方案数——不难发现这等价于求一张图的生成树个数,矩阵树定理解...

Educational Codeforces Round 118 (Rated for Div. 2) - F. Tree Coloring 题解

title: Codeforces-Edu118(Div.2)F. Tree Coloring
date: 2021-12-12 23:17:43
tags: [codeforces,div2,cpp,problem F,fft,divide and conquer,merge]
题意
给定一棵树,要求计算,给节点染色,要求每个节点 \(c_k \neq c_{p_k} - 1\) ,统计方案数 \((mod\ \ 998\ 244\ 353)\)
思路
容斥枚举破坏 \(i\) 个条件下的方案数,对于每个节点,都有出度种方法造成 \(1\) 个贡献,对于每个节点的生成函数即为
\[g(x...

T233514 B. 积木大赛【省选计划 · 模拟赛 #16】

摘要
篱笆刷色。支持:

所有子区间代价和。
区间加等差数列。


考虑贡献。首先每个 \(a_i\) 贡献所有以其为首的序列 \(a_i\),即 \(\displaystyle\sum_{i=1}^na_i(n-i+1)\)。
考虑差分数组 \(b_i\),贡献为 \(\displaystyle\sum_{i=2}^n\max(b_i,0)(i-1)(n-i+1)\)。
考虑插入一个等差数列。
对于首位的贡献,为 \(\displaystyle\sum_{i=l}^{r}v(i-l+1)(n-i+1)\)。可以 \(\mathcal{O}(1)\) 算。
\[\sum_{i=l}^r(n...

居家必备多项式板子

常用的操作都在这。MTT啥的就算了(
NTT +多项式逆+开根(\(f[0]=1\))+带余除法+求导+积分+ ln + exp +多项式快速幂(\(f[0]=1\))+分治NTT
#include<bits/stdc++.h>
#define int long long
#define pc(x) putchar(x)
#define clr(f,n) memset(f,0,sizeof(int)*n)
#define cpy(f,g,n) memcpy(f,g,sizeof(int)*n)
#define rev(f,n) reverse(f,f+n)
using names...

luogu P5406 [THUPC2019]找树

https://www.luogu.com.cn/problem/P5406
首先要意识到这题不是最优化问题,而是计数类问题(光这点就不简单了)
考虑矩阵树定理计算的是什么
\[\sum_{T}\prod w_{e\in T}
\]这里\(\prod\)不一定是乘法,题目给出的这几个运算爷可以
于是乎可以构造集合幂级数\(x^{w}\),注意到\(FWT\)是线性运算,可以叠加,先\(FWT\)完,求个行列式,然后再\(IDFT\)回去即可
code:
#include<bits/stdc++.h>
#define ll long long
#define mod 9982443...

文章标题:分治 fft 的一种 nlogn 做法
文章链接:https://www.dianjilingqu.com/51151.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>