【文文殿下】【洛谷】分治NTT模板

【文文殿下】【洛谷】分治NTT模板

题解

可以计算每一项对后面几项的贡献，然后考虑后面每一项，发现这是一个卷积，直接暴力NTT就行了，发现它是一个有后效性的，我们选择使用CDQ分治。

Tips:不能像通常CDQ分治一样直接 每次递归两边，然后处理。应该先递归左边，然后处理，再递归右边，保证右边的所有需要的转移已经被计算出来。

参考代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
const int p(998244353);
int mul(int a,int b) {return 1LL*a*b%p;
}
int inc(int a,int b) {a+=b;return a>=p?a-p:a;
}
int dec(int a,int b) {a-=b;return a<0?a+p:a;
}
int exp(int a,int b,int p) {if(b<0) b+=p-1;int ret=1,base(a);while(b) {if(b&1) ret=mul(ret,base);base=mul(base,base);b>>=1;}return ret;
}
void dft(int *a,int n,int inv) {for(int i = 1,j=n>>1;i<n-1;++i) {if(i<j) swap(a[i],a[j]);int k = n>>1;while(j>=k) j-=k,k>>=1;j+=k;}for(int j = 2;j<=n;j<<=1) {int wn=exp(3,(p-1)/j*inv,p);for(int i = 0;i<n;i+=j) {int w = 1;for(int k = i;k<i+(j>>1);++k) {int u(a[k]),t(mul(a[k+(j>>1)],w));a[k]=inc(u,t);a[k+(j>>1)]=dec(u,t);w=mul(w,wn);}}}if(inv==-1) {int iv = exp(n,p-2,p);for(int i =0;i<n;++i) a[i]=mul(a[i],iv);}
}
int n;
int g[maxn<<4],f[maxn<<4],tmp[maxn<<4],tmp2[maxn<<4];
void cdqntt(int l,int r) {if(l>r) return;if(l==r) return;int mid = (l+r)>>1;cdqntt(l,mid);int lmt = 1;while(lmt<=2*(r-l)) lmt<<=1;for(int i = 0;i<lmt;++i) tmp[i]=tmp2[i]=0;for(int i = 0;i<=r-l;++i) tmp2[i]=g[i];for(int i = l;i<=mid;++i) {tmp[i-l+1]=f[i];}dft(tmp,lmt,1);dft(tmp2,lmt,1);for(int i = 0;i<lmt;++i) tmp[i]=mul(tmp[i],tmp2[i]);dft(tmp,lmt,-1);for(int j = mid+1;j<=r;++j) {f[j]=inc(f[j],tmp[j-l+1]);}cdqntt(mid+1,r);
}
int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n;for(int i = 1;i<n;++i) cin>>g[i];f[0]=1;cdqntt(0,n-1);for(int i = 0;i<n;++i) cout<<f[i]<<' ';return 0;
}

转载于:.html