多项式$fft$,$ntt$,$fwt$初步

最近在学多项式和生成函数。

上课听$lnc$大神讲还是$mengbier$。

作为多项式的前置芝士，$fft,ntt$等是必学的。

在此记录一些关于$fft,ntt,fwt$的知识及例题。。。

---

 FFT：

　　应用在处理$sum _{i+j=k} f[i]*g[j]$的卷积上。

　　看网上大佬的博客，基本入了门吧。

　　自己的关于原理的一些见解：

　　　　多项式有系数表示和点值表示，两种表示方法可以相互转化。

　　　　FFT可以在$O(n*longn)$内解决多项式乘法。

　　　　具体是，点值表示的方法应用在多项式上是$O(n)$的。

　　　　那么如果能在快速时间内将多项式表示成点值，然后$O(n)$处理，再转化成多项式岂不美哉。

　　　　于是可一取单位根作为代入多项式的$x$，用分治算法处理即可。

　　板子：

#include<cstdio>
#include<iostream>
#include<cmath>
#define MAXN 362144
using namespace std;
const double PI=acos(-1);
struct Cp{
    double x,y;
    Cp(double xx=0,double yy=0){x=xx;y=yy;return ; }
    friend Cp operator +(Cp a,Cp b){return Cp(a.x+b.x,a.y+b.y); }
    friend Cp operator -(Cp a,Cp b){return Cp(a.x-b.x,a.y-b.y); }
    friend Cp operator *(Cp a,Cp b){return Cp(a.x*b.x-a.y*b.y,a.x*b.y+a.y*b.x); }
}a[MAXN],b[MAXN];
int n,m;
int lim=1,l=-1;
int ys[MAXN];
inline void FFT(Cp *x,const int &lim,const int &type){
    for(int i=0;i<lim;++i)if(i<ys[i])swap(x[i],x[ys[i]]);
    for(int i=1;i<lim;i<<=1){
        Cp tmp(cos(PI/i),sin(PI/i)*type);
        for(int j=0,I=i<<1;j<lim;j+=I){
            Cp w(1,0);
            for(int k=0;k<i;++k,w=w*tmp){
                Cp t1=x[j+k],t2=w*x[k+i+j];
                x[j+k]=t1+t2,x[k+i+j]=t1-t2;
            }
        }
    }
    return ;
}
int main(){
    //freopen("da.in","r",stdin);
    
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;++i)scanf("%lf",&a[i].x);
    for(int i=0;i<=m;++i)scanf("%lf",&b[i].x);
    n+=m;
    for(;lim<=n;lim<<=1,++l);
    for(int i=0;i<lim;++i)ys[i]=(ys[i>>1]>>1)|((i&1)<<l);
    FFT(a,lim,1);FFT(b,lim,1);
    for(int i=0;i<lim;++i)a[i]=a[i]*b[i];
    FFT(a,lim,-1);
    for(int i=0;i<=n;++i)printf("%d ",(int)(a[i].x/lim+0.5));
    puts("");
    
    return 0;
}

---

NTT：

　　原理和$FFT$类似。

#include<cstdio>
#include<iostream>
#define MAXN 2197152
#define LL long long
#define swap(x,y) (x^=y,y^=x,x^=y)
using namespace std;
const LL mod=998244353;
const LL G=3,inv_G=332748118;
int n,m;
int lim=1,l=-1;
int ys[MAXN];
LL a[MAXN],b[MAXN];
LL qpow(LL a,LL b){
    LL res=1LL;a%=mod;
    for(;b;b>>=1,a=a*a%mod)if(b&1)res=res*a%mod;
    return res%mod;
}
inline void NTT(LL *x,const int lim,const int type){
    for(int i=0;i<lim;++i)if(i<ys[i])swap(x[i],x[ys[i]]);
    for(int i=1;i<lim;i<<=1){
        const int delta=i<<1;
        const LL tmp=qpow(type==1?G:inv_G,(mod-1)/delta);
        for(int j=0;j<lim;j+=delta){
            LL w=1LL;
            for(int k=0;k<i;++k,w=w*tmp%mod){
                LL t1=x[j+k],t2=w*x[i+j+k]%mod;
                x[j+k]=(t1+t2)%mod,x[i+j+k]=(t1-t2+mod)%mod;
            }
        }
    }
    return ;
}
int main(){
    //freopen("da.in","r",stdin);
    
    scanf("%d%d",&n,&m);
    for(int i=0;i<=n;++i)scanf("%lld",&a[i]);
    for(int i=0;i<=m;++i)scanf("%lld",&b[i]);
    n+=m;for(;lim<n+2;lim<<=1,++l);
    for(int i=0;i<lim;++i)ys[i]=(ys[i>>1]>>1)|((i&1)<<l);
    NTT(a,lim,1);NTT(b,lim,1);
    for(int i=0;i<lim;++i)a[i]=a[i]*b[i]%mod;
    NTT(a,lim,-1);
    LL _inv=qpow(lim,mod-2);
    for(int i=0;i<=n;++i)printf("%lld ",a[i]*_inv%mod);
    puts("");
    
    return 0;
}

---

序列统计:

　　一道很棒的题，曾经出在达哥的模拟题中。

　　不过因为当时$M$的范围很小，$O(log(N)*M^2)$水过了。

　　然而此题必须得学原根了。

　　原根的两个知识点：

　　　　1>求法：拆$phi(M)$的质因子，从$2$暴枚，满足时当且仅当所有的$x^{frac{phi(y)}{d}}!=1$。

　　　　2>对于一个在$mod$意义下的原根$x$，$x^1,x^2,x^3.....x^{phi(mod)}$可以取遍$[1,phi(mod)]$的数，

　　　　其中，有费马小定理$a^{phi(p)}equiv 1(mod p)$，所以$x^{phi(mod)}$等同于$x^0$。

　　对这道题有什么用？

　　首先有倍增优化的$dp[i]$，表示某长度下，此时结果为$i$的方案数。

　　转移为$dp[i*j mod P]=sum dp[i]*b[j]$，好像每次转移只能$O(n^2)$。

　　此时考虑应用原根，乘法转化成了加法。

　　因为每个数都能用原根的次幂表示，所以可以直接用指数来表示一个数。

　　即为$dp[(i+j) mod phi(P)]=sum dp[i]*b[j]$

　　变成了我们会优化的形式，每次$NTT$加速即可。

　　注意$0in S$，不过$x>=1$，所以直接把$0$舍去即可。

　　$O(log(N)*M*log(M))$

---

 万径人踪灭:

　　题目背景保先生以及诗句的含义，啧啧。。。

　　没有看出来答案为$不连续回文序列个数-连续回文序列个数$。

　　求后者可以$O(n)$马拉车，也可以二分加$hash$。

LL Manacher(){
    LL res=0;
    int j=0;
    for(int i=1;i<=len;++i)nw[++j]='#',nw[++j]=rn[i];
    nw[++j]='#';
    int mx=0,id=0;
    //cout<<j<<endl;
    for(int i=1;i<=j;++i){
        p[i]=(i<mx)?min(p[2*id-i],mx-i):1;
        while(i-p[i]>=1&&i+p[i]<=j&&nw[i-p[i]]==nw[i+p[i]])++p[i];
        if(mx<i+p[i])mx=i+p[i],id=i;
        int t=p[i]-1;
        //if(rn[i]=='#')--t;
        (res+=(t+1)/2)%=mod;
        //cout<<i<<" "<<p[i]<<" "<<(t+1)/2<<endl;
    }
    //cout<<"qwq"<<endl;
    //scout<<res<<endl;
    return res;
}

　　前者是可将个数拆成$2^{cnt(a)+cnt(b)+(len and 1)}$。

　　求$cnt$，可以让$a$为$1$，$b$为$0$，$FFT$后$f[i]$即为$mid*2$处左右对称$a$的个数。

---

染色:

　　首先可以简单推一个$f[i]=frac{C(M,i)*C(N,i*S)*A(i*S,i*S)}{A(S,S)^i}*(M-i)^{N-S*i}$。

　　为钦定有$i$个颜色恰好出现了$S$次，我们想要的到$g[i]$为恰好有$i$个颜色出现了$S$次。

　　考虑有什么联系，发现因为不能保证剩下的颜色是否还会出现$S$次，所以会有重复的。

　　具体，$j>=i$，$g[j]$会在$f[i]$中算重了$C(j,i)$次，于是有：

　　$f[i]=sum_{j=i}^{m}C(j,i)*g[j]$

　　为二项式反演形式，变成：

　　$g[i]=sum_{j=i}^{m}-1^{j-i}C(j,i)*f[j]$

　　然后把阶乘拆掉就变成卷积的形式辣。

---