分治 fft 的一种 nlogn 做法
问题是给定 \(g_{1...n}\), 求 \(f_{0...n}\), 其中 \(f_0=1,f_i=\sum\limits_{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
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
{
vectorv;
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<>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;ii)swap(v[R[i]],v[i]);
for(int t=n>>1,d=1;d>=1)
for(int i=0;i1&&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<>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