首先是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