锐客网

  1. 首页 > it技术 > >

分治FFT/NTT

分治FFT

粘板子：
分治FFT/NTT
文章图片
分治FFT/NTT
文章图片

#include #include #include using namespace std; typedef long long ll; const int MOD = 998244353; const int N = 100050; const int M = N*3; template inline void read(T&x) { T f = 1,c = 0; char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1; ch=getchar(); } while(ch>='0'&&ch<='9'){c=c*10+ch-'0'; ch=getchar(); } x = f*c; } templateinline void Mod(T&x){if(x>=MOD)x-=MOD; } int fastpow(int x,int y) { int ret = 1; while(y) { if(y&1)ret=1ll*ret*x%MOD; x=1ll*x*x%MOD; y>>=1; } return ret; } int inv(int x){return fastpow(x,MOD-2); } int to[M],lim,L,LL[M]; void init(int len) { lim=LL[2]=1; while(lim>1]>>1)|((i&1)<<(L-1))); } void ntt(int*a,int len,int k) { for(int i=0; i>1; i++)swap(a[i],a[len-i]); int Inv = inv(len); for(int i=0; i>1; cdq(l,mid); get_lim(2*(r-l+1)); for(int i=0; i
View Code
【分治FFT/NTT】转载于:https://www.cnblogs.com/LiGuanlin1124/p/11162009.html

    推荐阅读


      上一篇：扩散

      下一篇：Photoshop教程｜合成篇｜寂静的森林