首页 学习笔记,数论

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

$FWT,FMT$都是解决位运算卷积的优秀方法(或者子集变换)

$FWT$根据不同的核心代码可以解决不同的位运算卷积(如或,与,异或),而$FMT$主要解决子集并和子集交的问题(也就是与、交)

$$ \forall i\quad c_i=\sum_{i=j\oplus k}a_jb_k $$


操作流程

类似于$FFT$一样,先把原来的$A,B$变换成$fwt_A,fwt_B$从而得到$fwt_C$然后再逆变换成$C$回来,从而求得答案。时间复杂度是$\mathcal O(n\log n)$


或($or$)

$$ \forall i\quad c_i=\sum_{i=j| k}a_jb_k $$

当$i=j|k$时,很显然有$k|i=i\quad j|i=i\quad (j|k)|i=i$

所以对于一个初始序列$A$我们考虑构造$fwt_A[i]=\sum_{j|i=i}a_j$

所以就有

$$ \begin{align} \forall i\quad fwt_A[i]*fwt_B[i]&=\Bigg (\sum_{j|i=i}A_j \Bigg )\Bigg(\sum_{k|i=i}B_k\Bigg )\\\\ &=\sum_{(j|k)|i=i}A_jB_k\\\\ &=fwt_C[i] \end{align} $$

那么问题来了,怎么把$A$变成$fwt_A$呢?考虑类似$FFT$一样分治下去

假设我们当前要求的为$F$(也就是变换后的$fwt$),根据最高位显然可以分成为$0、1$的两部分。我们假设为序列$F_0,F_1$.因为它们已经递归求解了,所以现在看怎么更新$F$

注意,当前是并没有考虑最高位的(也就是最高位默认为$0$)现在考虑最高位的不同会造成什么影响

因为$F_0$最高位为$0$,所以他的贡献只有$F_0$

因为$F_1$最高位为1,$0|1=1$,所以$a_0$中的答案是可以加上去的,也就是$F_0+F_1$

所以

$$ F= \begin{cases} merge(F_0,F_1+F_0)\\ A_i\quad\quad F.size=1 \end{cases} $$

举个例子,我们有$5=000101_2、37=100101_2$两个数,当$a$的长度为$64=1000000_2$时,他们分别在$F_0、F_1$的相同位置里。

很显然,如果有$j|5=5$,那么也一定会有$j|37=37$,所以$a_1$那里的答案要加上$a_0$

逆变换

现在问题变成了我们已知$F$,如何求得原来的$A$

显然,因为我们合并的时候$F_0$并没有改变,而$F_1$是加上了一个$F_0$的

所以可得

$$ A=\begin{cases}merge(A_0,A_1-A_0)\\F_i\quad\quad A.size=1\end{cases} $$

发现只有符号不同,所以代码合并一下

void FWT_or(modint f[],modint op=1){
    for(int len=2,k=1;len<=n;len<<=1,k<<=1)
    for(int i=0;i<n;i+=len)
    for(int j=0;j<k;j++)
    f[i+j+k]+=f[i+j]*op;
}

与(and)

这个和上面的或差不多的推导方式。最终得出

$$ F=\begin{cases}merge(F_0+F_1,F_1)\\A_i\quad\quad F.size=1\end{cases} $$

逆变换就是

$$ A=\begin{cases}merge(A_0-A_1,A_1)\\F_i\quad\quad A.size=1\end{cases} $$

void FWT_and(modint f[],modint op=1){
    for(int len=2,k=1;len<=n;len<<=1,k<<=1)
    for(int i=0;i<n;i+=len)
    for(int j=0;j<k;j++)
    f[i+j]+=f[i+j+k]*op;
}

异或(xor)

$$ \forall i\quad c_i=\sum_{i=j\oplus k}a_jb_k $$

异或比较麻烦,但是根据之前或和与来看,这个东西肯定是和$fwt_A、A$有种奇妙的线性关系

那我们就假设

$$ fwt_A[i]=\sum_{j=0}^ng(i,j)A_j $$

要满足$fwt_C=fwt_A\times fwt_B$,所以我们要让$g$满足

$$ \begin{align} \sum_{i=0}^ng(x,j)C_i&=\Bigg (\sum_{j=0}^ng(x,j)A_j\Bigg )\Bigg (\sum_{k=0}^ng(x,k)B_k\Bigg ) \end{align} $$

根据我们要求的,把$C$代换一下

$$ \begin{align} \sum_{i=0}^ng(x,j)\sum_{i=j\oplus k}A_jB_k&=\Bigg (\sum_{j=0}^ng(x,j)A_j\Bigg )\Bigg (\sum_{k=0}^ng(x,k)B_k\Bigg )\\ \sum_{i=0}^n\sum_{i=j\oplus k}g(x,j)A_jB_k&=\sum_{j=0}^n\sum_{k=0}g(x,j)g(x,k)A_jB_k \end{align} $$

因为异或是不进位加法,所以这里$j\oplus k≤n$我们就可以枚举求和顺序

$$ \begin{align} \sum_{j=0}^n\sum_{k=0}^ng(x,j\oplus k)A_jB_k&=\sum_{j=0}^n\sum_{k=0}^ng(x,j)g(x,k)A_jB_k \end{align} $$

那只要下面这个满足就可以了

$$ g(x,j\oplus k)=g(x,j)g(x,k) $$

想一想什么操作满足这个

回到异或的性质,相同为$0$,不同为$1$。所以猜想答案会和$j,k$中的$1$有关系

因为如果不同,个数不变,相同的话要么不变,要么$-2$,所以个数和的奇偶性不会变。但是这里是乘法啊!!

(那就把它放在指数位置吧)

所以我们令

$$ g(x,y)=(a)^{x\cap y} $$

因为奇偶性不变,所以我们要让$a^i=a^{i\%2}$,易知$a=±1$

我们考虑$x\cap y=popcount(x\&y)$($popcount$就是这个数在二进制下$1$的个数)会怎么变

类比之前的与、或运算,假设当前已知$fwt_0、fwt_1$现在考虑高位$01$的贡献

对于$fwt_0$因为高位无论$01$都不会改变$popcount$的值,所以方案就是$fwt_0+fwt_1$

对于$fwt_1$,只有高位为$1$时,$popcount$会$+1$所以方案就是$fwt_0+a\times fwt_1$

这么看来$1、-1$都是可以的。但是当我们做你变换的时候就相当于解这个方程

$$ \begin{cases} X=fwt_0+fwt_1\\ Y=fwt_0+a\times fwt_1 \end{cases} $$

其中已知$X、Y$。但当$a=1$时,这个是无解的啊!!!所以只能选$-1$了

所以最后

$$ g(x,y)=(-1)^{x\cap y} $$

最终变换就是

$$ F=\begin{cases}merge(F_0+F_1,F_0-F_1)\\A_i\quad\quad F.size=1\end{cases} $$

逆变换

$$ A=\begin{cases}merge(\frac{A_0+A_1}{2},\frac{A_0-A_1}{2})\\F_i\quad\quad A.size=1\end{cases} $$

void FWT_xor(modint f[],modint op=1){
    for(int len=2,k=1;len<=n;len<<=1,k<<=1)
    for(int i=0;i<n;i+=len)
    for(int j=0;j<k;j++){
        f[i+j]+=f[i+j+k];
        f[i+j+k]=f[i+j]-f[i+j+k]-f[i+j+k],
        f[i+j]*=op,f[i+j+k]*=op;
    }
}

Code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=998244353;
const int N=2e5+9;
inline int read(){
    int f=0,x=0;
    char ch=getchar();
    while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
int n,m;
struct modint{
    int a;
    modint(int a=0):a(a){}
    inline int inv(int x,int base){
        int res=1;
        while(base){
            if(base&1)res=res*x%p;
            x=x*x%p;base>>=1;
        }return res;
    }
    void operator +=(const modint x){a=(a+x.a)%p;}
    void operator *=(const modint x){a=(a*x.a)%p;}
    void operator =(const int x){a=x%p;}
    modint operator +(const modint x){return modint((a+x.a)%p);}
    modint operator -(const modint x){return modint(((a-x.a)%p+p)%p);}
    modint operator *(const modint x){return modint((a*x.a)%p);}
    modint operator /(const modint x){return modint(a*inv(x.a,p-2)%p);}
    
}a[N],b[N],A[N],B[N];
inline void init(){
    for(int i=0;i<n;i++)a[i]=A[i];
    for(int i=0;i<n;i++)b[i]=B[i];
}
inline void get(){
    for(int i=0;i<n;i++)a[i]*=b[i];
}
void FWT_or(modint f[],modint op=1){
    for(int len=2,k=1;len<=n;len<<=1,k<<=1)
    for(int i=0;i<n;i+=len)
    for(int j=0;j<k;j++)
    f[i+j+k]+=f[i+j]*op;
}
void FWT_and(modint f[],modint op=1){
    for(int len=2,k=1;len<=n;len<<=1,k<<=1)
    for(int i=0;i<n;i+=len)
    for(int j=0;j<k;j++)
    f[i+j]+=f[i+j+k]*op;
}
void FWT_xor(modint f[],modint op=1){
    for(int len=2,k=1;len<=n;len<<=1,k<<=1)
    for(int i=0;i<n;i+=len)
    for(int j=0;j<k;j++){
        f[i+j]+=f[i+j+k];
        f[i+j+k]=f[i+j]-f[i+j+k]-f[i+j+k],
        f[i+j]*=op,f[i+j+k]*=op;
    }
}
inline void write(){
    for(int i=0;i<n;i++)
        printf("%lld%c",a[i].a," \n"[i==n-1]);
}
signed main(){
    m=read(),n=1<<m;
    for(int i=0;i<n;i++)A[i]=read();
    for(int i=0;i<n;i++)B[i]=read();
    init();FWT_or(a),FWT_or(b),get(),FWT_or(a,p-1);write();
    init();FWT_and(a),FWT_and(b),get(),FWT_and(a,p-1);write();
    init();FWT_xor(a),FWT_xor(b),get(),FWT_xor(a,modint(1)/2);write();
    return 0;
}

「JOI 2018 Final」毒蛇越狱
$\quad\quad$这个题就很好的运用到了子集和变换($FMT$)

$\quad\quad$首先很好想,我们可以 $3^{cnt2}$ 枚举子集是什么,但是这样肯定会超时,我们考虑怎么优化

$\quad\quad$注意到当 $?$ 的个数很多时,相应的 $0,1$ 的个数就会变少,所以我们不妨考虑从这个入手。这里我们以$1$为例:

$\quad\quad$假设我们有了 $11000????$ ,我们要让有 $?$ 的地方把 $0,1$ 都要取一次,那我们不妨就假设 $?$ 为 $1$ ,就变成了 $110001111$ ,此时我们加上这个的子集和,就成功地让每一个 $?$ 都取过$0,1$了。但是我们会发现一个问题,原来是 $1$ 的地方也取了 $0$,但是事实上这是不被允许的,怎么办呢?容斥一下就好了!所以我们再枚举有$1$的地方组成的集合 $T$ 的子集 $S$ ,发现容斥系数就是原集合的 $-1^{pop(T-S)}$ 。然后时间复杂度是枚举子集的 $3^{cnt1}$。这样下来,我们对于 $?$ 多的和 $1$ 多的分开处理即可。

$\quad\quad$但还是卡不过去啊?想一想,好像 $0$ 没用过,这个能不能像 $1$ 一样呢?当然可以!虽然没有子集和,但是我们可以利用超集和。此时相当于把 $?$ 看成 $0$,相应的容斥即可。

关于求子集和和超集和的方法,我们考虑他们是个什么东西。子集和就是原来固定 $0$ ,剩下随便取,超集和就是固定$1$,剩下随便取。想一想 $FWT_or$ 和 $FWT_and$ ,好像就是求子集和和超集和的!那么预处理一下就好了。

这样的话,我们的复杂度就会是 $\mathcal O (n\log n+q3^{n/3})$ 就可以过了!

#include<bits/stdc++.h>
#define get(x) ((x)&1?-1:1)
using namespace std;
const int N=4e6+9;
inline int read(){
    int f=0,x=0;
    char ch=getchar();
    while(!isdigit(ch)){f|=(ch=='-');ch=getchar();}
    while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
    return f?-x:x;
}
int l,q,sz;
int pop[N];
inline void fwt_or(int A[],int n,int op){
    for(int len=2,k=1;len<=n;len<<=1,k<<=1)
    for(int i=0;i<n;i+=len)
    for(int j=0;j<k;j++)
    A[i+j+k]+=A[i+j]*op;
    return;
}
inline void fwt_and(int A[],int n,int op){
    for(int len=2,k=1;len<=n;len<<=1,k<<=1)
    for(int i=0;i<n;i+=len)
    for(int j=0;j<k;j++)
    A[i+j]+=A[i+j+k]*op;
    return;
}
int f[N],g[N],w[N];
char s[N];
inline void init(){
    l=read(),q=read();
    scanf("%s",s);
    sz=1<<l;
    for(int i=1;i<=sz;i++)pop[i]=pop[i>>1]+(i&1);
    for(int i=0;i<sz;i++)f[i]=g[i]=w[i]=s[i]-'0';
    fwt_or(f,sz,1);fwt_and(g,sz,1);
    return;
}
int x,y,z,ans;
int main(){
    init();
    while(q--){
        scanf("%s",s+1);
        x=y=z=ans=0;
        for(int i=1;i<=l;i++){
            (x<<=1)|=(s[i]=='0');
            (y<<=1)|=(s[i]=='1');
            (z<<=1)|=(s[i]=='?');
        }
        int mn=min(pop[x],min(pop[y],pop[z]));
        if(mn==pop[x]){
            ans=g[y];
            for(int i=x;i;--i&=x)ans+=get(pop[i])*g[y|i];
        }else if(mn==pop[y]){
            int now=(sz-1)^x;
            ans=f[now];
            for(int i=y;i;--i&=y)ans+=get(pop[i])*f[now-i];
        }else{
            ans+=w[y];
            for(int i=z;i;--i&=z)ans+=w[i|y];
        }
        printf("%d\n",ans);
    }
    return 0;
}



文章评论

目录