一些多项式的整理-白红宇

一些多项式的整理

阅读量：4581 次

发布时间：2019-06-09

本文共 1692 字，大约阅读时间需要 5 分钟。

卷积

\(c=a \otimes b\)

\(c_i=\sum_{j=0}^{i} a_j b_{i-j}\)

卷积运算的性质也就是多项式乘法的性质：

交换律:\(a \otimes b=b \otimes a\)

结合律:\((a \otimes b) \otimes c=a \otimes (b \otimes c)\)

分配律:\((a+b) \otimes c=a \otimes c+b \otimes c\)

FFT

用于优化两个多项式的卷积，时间复杂度\(O(nlogn)\)。

struct node{    double x,y;    inline node operator + (const node &b)const{return (node){x+b.x,y+b.y};}    inline node operator - (const node &b)const{return (node){x-b.x,y-b.y};}    inline node operator * (const node &b)const{return (node){x*b.x-y*b.y,y*b.x+x*b.y};}}a[N],b[N];int pos[N];inline void init(){    for (n=1;n<=na+nb;n<<=1,l++);    For(i,1,n) pos[i]=(pos[i>>1]>>1)|((i&1)<<(l-1));}inline void FFT(node *a,int f){    For(i,0,n-1) if (i

NTT

用来处理有特定模数(如\(998244353\))的卷积，把\(FFT\)的单位复根换成原根。

const int mod = 998244353;inline int power(int a,int b){    int ret=1;    for (;b;b>>=1,a=1ll*a*a%mod) if (b&1) ret=1ll*ret*a%mod;    return ret;}inline int Mod(int x){return x=(x<0)?x+mod:x,x=(x>=mod)?x-mod:x,x;}inline void NTT(int n,vector
    
     &a,int f){    a.resize(n);    For(i,0,n-1) if (i

倍增FFT

套个卡速米就行了。

inline vector
    
      Power(vector
     
      a,int b){    vector
      
        ret=a;b--;    for (;b;b>>=1,a=Mul(a,a)) if (b&1) ret=Mul(ret,a);    return ret;}

分治FFT

\(f_i=\sum_{j=1}^{i}f_{i-j}g_j\)

套个\(CDQ\)就行了。

inline void Solve(int l,int r){    if (l==r) return;    int mid=l+r>>1;Solve(l,mid);    vector
    
     A,B,C;    For(i,l,mid) A.push_back(f[i]);    For(i,0,r-l) B.push_back(g[i]);    C=Mul(A,B);    For(i,mid+1,r) f[i]=Mod(f[i]+C[i-l]);    Solve(mid+1,r);}