快速莫比乌斯/沃尔什变换 (FMT/FWT)

· · 个人记录

FMT与FWT

\large by~ctldragon

一、快速莫比乌斯变换

快速莫比乌斯变换简称 FMT ，用于快速计算位运算卷积。

我们定义 A 的莫比乌斯变换为 FMT(A) ，A_i 为 A 的第 i 项。

1、或卷积

我们要求：\large C_x=\sum\limits_{i\cup j=x}A_iB_j

若有 \large FMT(A)_i\times FMT(B)_i=FMT(C)_i ，我们就能通过逆变换快速求出 C 出来。

定义：\large FMT(A)_n=\sum\limits_{i\in n}A_i ，其中 i,n 都是二进制表示的集合。

\large FMT(A)_x\times FMT(B)_x=\sum\limits_{i\in x}A_i\sum\limits_{j\in x}B_j=\sum\limits_{i\in x}\sum\limits_{j\in x}A_iB_j=\sum\limits_{k\in x}\sum\limits_{i\cup j=k}A_iB_j=\sum\limits_{k\in x}C_k=FMT(C)_x

所以利用子集和可以加速求出或卷积。

那如何快速求出子集和捏？不就是高维前缀和了捏！

高维前缀和：\large S_i=\sum\limits_{i\cup j=i}A_j

code：

void FMT(int *f,int n,int op)//op=1为正变换，op=-1为逆变换
{
    for(int i=0;i<n;++i)
        for(int j=0;j<(1<<n);++j)
            if(j&(1<<i))f[j]+=f[j^(1<<i)]*op;
}

2、与卷积

我们要求：\large C_x=\sum\limits_{i\cap j=x}A_iB_j

若有 \large FMT(A)_i\times FMT(B)_i=FMT(C)_i ，我们就能通过逆变换快速求出 C 出来。

定义：\large FMT(A)_n=\sum\limits_{n\in i}A_i ，其中 i,n 都是二进制表示的集合。

\large FMT(A)_x\times FMT(B)_x=\sum\limits_{x\in i}A_i\sum\limits_{x\in j}B_j=\sum\limits_{x\in i}\sum\limits_{x\in j}A_iB_j=\sum\limits_{x\in k}\sum\limits_{i\cap j=k}A_iB_j=\sum\limits_{x\in k}C_k=FMT(C)_x

这不就是高维后缀和了捏！

高维后缀和：\large S_i=\sum\limits_{i\cap j=i}A_j

code：

void FMT(int *f,int n,int op)//op=1为正变换，op=-1为逆变换
{
    for(int i=0;i<n;++i)
        for(int j=0;j<(1<<n);++j)
            if(j&(1<<i))f[j^(1<<i)]+=f[j]*op;
}

二、快速沃尔什变换

快速沃尔什变换简称 FWT ，同样用于快速计算位运算卷积。

我们定义 A 的沃尔什变换为 FWT(A) ，A_i 为 A 的第 i 项。

1、异或卷积

定义：\large FWT(A)_x=\sum\limits_{k=0}^{2^n-1}(-1)^{|x\wedge k|}A_k

\large FWT(C)_x=\sum\limits_{k=0}^{2^n-1}(-1)^{|x\wedge k|}C_k \large ~~~~~~~~~~~~~~~~~~=\sum\limits_{k=0}^{2^n-1}(-1)^{|x\wedge k|}\sum\limits_{i=0}^{2^n-1}\sum\limits_{j=0}^{2^n-1}[i\oplus j=k]A_iB_j \large ~~~~~~~~~~~~~~~~~~=\sum\limits_{i=0}^{2^n-1}\sum\limits_{j=0}^{2^n-1}(-1)^{|(i\oplus j)\wedge x|}A_iB_j \large ~~~~~~~~~~~~~~~~~~=\sum\limits_{i=0}^{2^n-1}\sum\limits_{j=0}^{2^n-1}(-1)^{|x\wedge i|}A_i·(-1)^{|x\wedge j|}B_j \large ~~~~~~~~~~~~~~~~~~=(\sum\limits_{i=0}^{2^n-1}(-1)^{|x\wedge i|}A_i)(\sum\limits_{j=0}^{2^n-1}(-1)^{|x\wedge j|}B_j) \large ~~~~~~~~~~~~~~~~~~=FWT(A)_x \times FWT(B)_x

和高维前缀和相似，我们对每一位依次考虑。对于第 i 位和一个不包含 i 的集合 S ，设 x=a_S,y=a_{S+2^i} ，则有新的 a_S=x+y,a_{S+2^i}=x-y。

code：

void FWT(int *f,int n,int op)
{
    for(int i=1;i<(1<<n);i<<=1)
        for(int j=0;j<(1<<n);j+=(i<<1))
            for(int k=j;k<j+i;++k)
            {
                int x=f[k],y=f[k+i];
                if(op==1)f[k]=x+y,f[k+i]=x-y;
                else f[k]=(x+y)/2,f[k+i]=(x-y)/2;
            }
}

是不是很简单

当然，FMT 也可以计算或卷积和与卷积，但懒得打了（咕咕咕

2、子集卷积

咕咕咕

3、子集卷积 exp

咕咕咕

4、多项式复合集合幂级数