分治NTT

标签：return int s2 分治 NTT lim

首先是NTT的板子。

int cnt[N];
void NTT(int a[],int lim,bool type){
	for(int i=0;i<(1<<lim);i++)cnt[i]=(cnt[i>>1]>>1)|((i&1)<<(lim-1));
	for(int i=0;i<(1<<lim);i++)if(i<cnt[i])swap(a[i],a[cnt[i]]);
	for(int i=1;i<(1<<lim);i<<=1){
		int dd=qp(type?3:inv,(mod-1)/i>>1);
		for(int j=0;j<(1<<lim);j+=i<<1){
			int t=1;
			for(int k=0;k<i;k++){
				int x=t*a[i+j+k]%mod;
				a[i+j+k]=(a[j+k]-x+mod)%mod;
				a[j+k]=(a[j+k]+x)%mod;t=t*dd%mod;
			}
		}
	}
	if(type)return;int nowInv=qp(1<<lim,mod-2);
	for(int i=0;i<(1<<lim);i++)a[i]=a[i]*nowInv%mod;
}

然后是分治 NTT。分治 NTT 其实就是一个NTT的板子，然后通过分治的方法（类似cdq分治）来快速计算，复杂度是 \(O(N\log^2N)\)，也很好理解。

#include<bits/stdc++.h>
//#define feyn
#define int long long
using namespace std;
const int N=1<<17;
const int mod=998244353;
const int inv=(mod+1)/3;
inline void read(int &wh){
    wh=0;int f=1;char w=getchar();
    while(w<'0'||w>'9'){if(w=='-')f=-1;w=getchar();}
    while(w<='9'&&w>='0'){wh=wh*10+w-'0';w=getchar();}
    wh*=f;return;
}
inline int qp(int s1,int s2){
	if(s2==1)return s1;int an=qp(s1,s2>>1);
	if(s2&1)return an*an%mod*s1%mod;else return an*an%mod;
}

int cnt[N];
void NTT(int a[],int lim,bool type){
	for(int i=0;i<(1<<lim);i++)cnt[i]=(cnt[i>>1]>>1)|((i&1)<<(lim-1));
	for(int i=0;i<(1<<lim);i++)if(i<cnt[i])swap(a[i],a[cnt[i]]);
	for(int i=1;i<(1<<lim);i<<=1){
		int dd=qp(type?3:inv,(mod-1)/i>>1);
		for(int j=0;j<(1<<lim);j+=i<<1){
			int t=1;
			for(int k=0;k<i;k++){
				int x=t*a[i+j+k]%mod;
				a[i+j+k]=(a[j+k]-x+mod)%mod;
				a[j+k]=(a[j+k]+x)%mod;t=t*dd%mod;
			}
		}
	}
	if(type)return;int nowInv=qp(1<<lim,mod-2);
	for(int i=0;i<(1<<lim);i++)a[i]=a[i]*nowInv%mod;
}

int m,f[N],g[N],a[N],b[N];
void solve(int l,int r,int lim){
	if(lim<=0)return;int mid=(l+r)>>1;
	solve(l,mid,lim-1);
	for(int i=0;i<(1<<lim);i++)a[i]=(l+i<=mid)?f[l+i]:0;
	for(int i=0;i<(1<<lim);i++)b[i]=g[i];
	NTT(a,lim,true);NTT(b,lim,true);
	for(int i=0;i<(1<<lim);i++)a[i]=a[i]*b[i]%mod;
	NTT(a,lim,false);
	for(int i=mid+1;i<=r;i++)f[i]=(f[i]+a[i-l])%mod;
	solve(mid+1,r,lim-1);
}

signed main(){
	
	#ifdef feyn
	freopen("in.txt","r",stdin);
	#endif
	
	read(m);int n=1;while((1<<n)<m)++n;
	for(int i=1;i<m;i++)read(g[i]);f[0]=1;
	solve(0,(1<<n)-1,n);
	for(int i=0;i<m;i++)printf("%lld ",f[i]);
	
	return 0;
}

然后是两个例题。

P4841

用 \(f_{x}\) 代表大小为 \(x\) 的图的答案，\(g_x\) 代表不要求联通的方案。于是显然有：

\[\begin{aligned} f_{x}&=\sum\limits_{i=1}^{x-1}\binom{x}{i}f_{i}g_{x-i}\\ &=\sum\limits_{i=1}^{x-1}x!\dfrac{f_i}{i!}\dfrac{g_{x-i}}{(x-i)!} \end{aligned} \]

然后就是分治 NTT 的板子了。

标签：return,int,s2,分治,NTT,lim
From： https://www.cnblogs.com/Feyn/p/17113578.html