LOADING STUFF...

FMT/FWT学习笔记

技术分享4年前 (2020)更新 技术分享
1,935 0 0

目录

FMT/FWT学习笔记

FMT/FWT是算法竞赛中求or/and/xor卷积的算法,数据处理中也有应用。

网上的命名方法有很多。

这里我们选这个博客的,把AND/OR命名为FMT,XOR命名为FWT

如果是整数,我们认为\(\cup\)\(\cap\)运算是二进制下的,也就是\(\text{|和&}\),这可以帮我们理解之后的集合幂级数。

FMT 快速莫比乌斯变换 OR卷积

与FMT可以求出

\[C=\sum_i C_i=\sum_i\sum_{j\cup k=i}A_j*B_k=A\cup B \]

因为前缀的并是前缀,容易得到过程是把A、B求子集前缀和,得到FMTor数组

\[FMT(A)_n=\sum_{i \subseteq n}A_i \]

与FFT类似,FMTor数组直接乘起来就得到了C的FMTor数组,证明如下:

\[FMT(A)_n * FMT(B)_n=\sum_{i \subseteq x} A_{i} \sum_{j \subseteq x} B_{j}=\sum_{i, j \subseteq x} A_{i} B_{j}=\sum_{k \subseteq x} \sum_{i \cup j=k} A_{i} B_{j}=FMT(C)_n \]

最后换回去(子集和变原数组)就得到了C

至于具体怎么算前缀和,挂张图,想必大家见过很多次了吧(箭头表示加法)

FMT/FWT学习笔记

如上图,讨论这一层的1在不在下一个集合即可。

代码:

const int N = 2e5+200;
const ll mod = 998244353;
int a[N];
void FMTor(int *a,int n,int opt){
    for(int l=2;l<=n;l<<=1){
        int m=l>>1;
        for(int *g=a;g!=a+n;g+=l){
            for(int k=0;k<m;k++){
                if(opt==1) g[k+m]=(g[k+m]+g[k])%mod;
                else g[k+m]=(g[k+m]-g[k]+mod)%mod;
            }
        }
    }
}

跟FFT非常的像…

AND卷积

\[C=\sum_i C_i=\sum_i\sum_{j\cap k=i}A_j*B_k=A\cap B \]

然后猜测FMTand为后缀和(后缀的交为后缀),

\[FMT(A)_n=\sum_{n\subseteq i} A(i) \]

同样的,证明:

\[FMT(A)_n * FMT(B)_n=\sum_{n\subseteq i} A_i\sum_{n\subseteq j} B_j=\sum_{n\subseteq i,j} A_i*B_j=\sum_{n\subseteq x}\sum_{i\cap j=x}A_i*B_j=FMT(C)_n \]

和OR是不是有几分相似?

const int N = 2e5+200;
const ll mod = 998244353;
int a[N];
void FMTand(int *a,int n,int opt){
    for(int l=2;l<=n;l<<=1){
        int m=l>>1;
        for(int *g=a;g!=a+n;g+=l){
            for(int k=0;k<m;k++){
                if(opt==1) g[k]=(g[k]+g[k+m])%mod;
                else g[k]=(g[k]-g[k+m]+mod)%mod;
            }
        }
    }
}

快速沃尔什变换(FWT/XOR卷积)

这个稍微难点

我们要求

\[C=\sum_i C_i=\sum_i\sum_{j\oplus k=i}A_j*B_k=A\oplus B \]

这里的FWT数组不是那么显然,考虑构造。

由于线性相关,令

\[FWT(A)_x=\sum_{i=0}^ng(x,i)A_i \]

那么

\[\sum_{i=0}^{n} g(x, i) C_{i}=\sum_{j=0}^{n} g(x, j) A_{j} \sum_{k=0}^{n} g(x, k) B_{k} \]

带入C的定义,

\[\sum_{j=0}^{n} \sum_{k=0}^{n} g(x, j \oplus k) A_{j} B_{k}=\sum_{j=0}^{n} \sum_{k=0}^{n} g(x, j) g(x, k) A_{j} B_{k} \]

对比系数,

\[g(x,j\oplus k)=g(x,j)g(x,k) \]

异或有一系列性质:

  1. \((j\cap x)\oplus (k\cap x)=(j\oplus k)\cap x\)

    不知道这个的可以讨论一波:在第\(i\)位,

    \[\begin{array}{|c|c|c|c|c|c|c|c|}j & k &x &j\cap x &k\cap x&(j\cap x)\oplus (k\cap x)&j \oplus k&(j\oplus k)\cap x\\0&0&0&0&0&0&0&0\\0&0&1&0&0&0&0&0\\0&1&0&0&0&0&1&0\\0&1&1&0&1&1&1&1\\1&0&0&0&0&0&1&0\\1&0&1&1&0&1&1&1\\1&1&0&1&1&0&0&0\\1&1&1&1&1&0&0&0\\\end{array} \]

  2. 异或前后1的个数奇偶性不变(对吧)

那么我们定义\(|x|\)为二进制下集合大小,即1的个数,g就可以赋值了

\[g(x, i)=(-1)^{|i \cap x|} \]

\[FWT(A)_{x}=\sum_{i=0}^{n}(-1)^{|i \cap x|} A_{i} \]

考虑怎么递推算这个东西,考虑加不加上区间长度i

由于枚举i为2的次幂从小到大,新加上i集合大小一定加一,系数乘负一,否则不变。

那么有:

\[A[j+k]=A_0[j+k]+A_0[j+k+i]\\A[j+k+i]=A_0[j+k]-A_0[j+k+i]\\ \]

反过来,解方程可以得到

\[A_0[j+k]=\frac{A[j+k]+A[j+k+i]}{2}\\A_0[j+k+i]=\frac{A[j+k]-A_[j+k+i]}{2}\\ \]

代码:

const int N = 2e5+200;
const int mod = 998244353;
const int inv2 = 499122177;
int a[N];
void FWT(int *a,int n,int opt){
    for(int l=2;l<=n;l<<=1){
        int m=l>>1;
        for(int *g=a;g!=a+n;g+=l){
            for(int k=0;k<m;k++){
                ll t=g[k+m];
                g[k+m]=(g[k]-g[k+m]+mod)%mod;
                g[k]=(g[k]+t)%mod;//草,有蝴蝶变换内味了
                //提醒一下这和FFT的区别:没有乘单位根
                if(opt==-1) g[k]=1ll*g[k]*inv2%mod,g[k+m]=1ll*g[k+m]*inv2%mod;
                //而且反演的时候也不一样
            }
        }
    }
}

就愉快地学完啦!是不是比FFT简单

© 版权声明

相关文章

暂无评论

您必须登录才能参与评论!
立即登录
暂无评论...