正文 

当前位置： 首页 > IT > java教程

浅谈快速沃尔什变换(代码片段)

hbyer hbyer     2023-02-27     658

关键词：

快速沃尔什变换(fwt)

(fwt)是一种快速计算位运算卷积的算法，一般包括按位或卷积，按位与卷积和异或卷积。

按位或(or)卷积

对于多项式(A,B,C)，定义(oplus)为卷积符号，即(Aoplus B = C)。

那么，按位或卷积就是：
[ C_k=sum_i~or~j=kA_icdot B_j ]
类比于(FFT)，现在，我们的任务就是找到一种变换，记这种变换为(fwt(A))，则要满足(fwt(A) imes fwt(B)=fwt(C))，其中( imes)表示每一位相乘，且(Aoplus B=C)。

经过前人的大力研究，可以发现：
[ fwt(A)_i=sum_j~or~i=iA_j ]
是满足性质的，证明很简单，直接带进去可得：
[ eginalign fwt(C)_k&=sum_j~or~k=ksum_a~or~b=kA_acdot B_b&=sum_a~or~k=kA_acdot sum_b~or~k=kB_b&=fwt(A)_kcdot fwt(B)_k endalign ]
即得证。

那么，考虑怎样快速的进行(fwt)变换。

然后有一个这样的式子：
[ fwt(A)= egincases (fwt(A_1),fwt(A_1)+fwt(A_2))&n>0A_0&n=0 endcases ]
其中，((A,B))表示把两个多项式的系数拼起来，感性理解一下就好了。

(A_1)表示多项式前半段，(A_2)表示后半段。

当(n=0)的时候显然，我们只需要关心上面那个是为什么就好了。

对于前半段的第(i)项，(i)的最高位肯定是(0)，那么后半段显然对他没有影响，前半段的影响就是(fwt(A_1)_i)。

对于后半段的第(i)项，(i)的最高位是(1)，所以最高位取(0)时是(fwt(A_1)_i)，取(1)时是(fwt(A_2)_i)，所以一共就是(fwt(A_1)+fwt(A_2))。

然后这玩意形式其实和(FFT)差不太多，复杂度也是(O(nlog n))。

代码：

void fwt_or(int *r) 
    for(int i=1;i<n;i<<=1)
        for(int j=0;j<n;j+=(i<<1))
            for(int k=0;k<i;k++)
                r[i+j+k]=(r[i+j+k]+r[j+k])%mod;

按位与(and)卷积

和上面差不多的，定义：
[ fwt(A)_i=sum_j&i=iA_i ]
证明也差不多，这里不赘述了。

那么，算的话就是：
[ fwt(A)= egincases (fwt(A_1)+fwt(A_2),fwt(A_2))&n>0A_0&n=0 endcases ]
只要考虑按位与的性质，高位为(1)时只能选高位为(1)的，否则都能选。

代码：

void fwt_and(int *r) 
    for(int i=1;i<n;i<<=1)
        for(int j=0;j<n;j+=(i<<1))
            for(int k=0;k<i;k++)
                r[j+k]=(r[i+j+k]+r[j+k])%mod;

异或(xor)卷积

这里的定义就不是很相同了。

定义：
[ fwt(A)_i=sum_j=0^n(-1)^cnt(i&j)A_j ]
其中，(i&j)表示按位与，(cnt(x))表示(x)二进制下(1)的个数。(这到底是怎么想到的。。)

带进去交换下枚举顺序可得：
[ eginalign fwt(C)_i&=sum_j=0^n(-1)^cnt(i&j)C_j&=sum_j=0^n(-1)^cnt(i&j)sum_aoplus b=jA_aB_b&=sum_a=0^nA_asum_b=0^nB_b(-1)^cnt(i&(aoplus b)) endalign ]
我们考虑下指数上的那一块东西：(cnt(i&(aoplus b)))，分情况讨论下这个与(cnt(i&a)+cnt(i&b))的关系：（由于多位和一位没有区别，这里只讨论一位）

若(i)为(0)，显然这一位不计入答案，不管。

若(a,b)都为(1)的话，(aoplus b=0)，不计入答案，但是注意到这里是((-1))的指数，其实((-1)^0=(-1)^2)，不妨看做是(2)，那么这两个相等。

若(a,b)有一个为(1)，前后显然相等，都为(1)。

若(a,b)都为(0)，显然也相等，都为(0)。

所以式子可以改写成这样：
[ eginalign fwt(C)_i&=sum_a=0^nA_asum_b=0^nB_b(-1)^cnt(i&a)+cnt(i&b)&=sum_a=0^n(-1)^cnt(i&a)A_asum_b=0^n(-1)^cnt(i&b)B_b&=fwt(A)_icdot fwt(B)_i endalign ]
所以，证毕。

那么，快速做这个的式子：
[ fwt(A)= egincases (fwt(A_1)+fwt(A_2),fwt(A_1)-fwt(A_2))&n>0A_0&n=0 endcases ]
具体的，考虑前一半的时候，最高位为(0)，直接加起来就好了。

对于后一半，最高位为(1)，如果选的数最高位也为(1)，(cnt)就多了(1)，也就是整体多乘了个(-1)，所以就是(fwt(A_1)-fwt(A_2))。

代码：

void fwt_xor(int *r) 
    for(int i=1;i<n;i<<=1)
        for(int j=0;j<n;j+=(i<<1))
            for(int k=0;k<i;k++) 
                int x=r[j+k],y=r[i+j+k];
                r[j+k]=(x+y)%mod,r[i+j+k]=(x-y)%mod;

逆沃尔什变换

知道了上面的，这玩意其实就很简单了。

对于按位或，就是知道了(fwt(A_1))和(fwt(A_1)+fwt(A_2))，求出两个分别是多少，直接减一下就完了：
[ ifwt(A)=(ifwt(A_1),ifwt(A_2)-ifwt(A_1)) ]
对于按位与，也差不多：
[ ifwt(A)=(ifwt(A_1)-ifwt(A_2),ifwt(A_2)) ]
对于异或，是知道(fwt(A_1)+fwt(A_2))和(fwt(A_1)-fwt(A_2))，那么加起来除以(2)就是第一个，减一下除以(2)就是第二个，即：
[ ifwt(A)=(fracifwt(A_1)+ifwt(A_2)2,fracifwt(A_1)-ifwt(A_2)2) ]

模板

给一个模板大全吧，题目来自luogu4717。

#include<bits/stdc++.h>
using namespace std;
 
void read(int &x) 
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;

 
void print(int x) 
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);

void write(int x) if(!x) putchar('0');else print(x);putchar('
');

const int maxn = 2e5+10;
const int mod = 998244353;
const int inv2 = 499122177;

int bit,n,a[maxn],b[maxn],c[maxn],ina[maxn],inb[maxn];

void fwt_or(int *r,int op) 
    for(int i=1;i<n;i<<=1)
        for(int j=0;j<n;j+=(i<<1))
            for(int k=0;k<i;k++)
                if(op==1) r[i+j+k]=(r[i+j+k]+r[j+k])%mod;
                else r[i+j+k]=(r[i+j+k]-r[j+k])%mod;


void fwt_and(int *r,int op) 
    for(int i=1;i<n;i<<=1)
        for(int j=0;j<n;j+=(i<<1))
            for(int k=0;k<i;k++)
                if(op==1) r[j+k]=(r[i+j+k]+r[j+k])%mod;
                else r[j+k]=(r[j+k]-r[i+j+k])%mod;


void fwt_xor(int *r,int op) 
    for(int i=1;i<n;i<<=1)
        for(int j=0;j<n;j+=(i<<1))
            for(int k=0;k<i;k++) 
                int x=r[j+k],y=r[i+j+k];
                if(op==1) r[j+k]=(x+y)%mod,r[i+j+k]=(x-y)%mod;
                else r[j+k]=1ll*(x+y)*inv2%mod,r[i+j+k]=1ll*(x-y)*inv2%mod;
            


int main() 
    read(bit);n=1<<bit;
    for(int i=0;i<n;i++) read(ina[i]);
    for(int i=0;i<n;i++) read(inb[i]);
    // or
    memcpy(a,ina,sizeof ina);memcpy(b,inb,sizeof inb);
    fwt_or(a,1),fwt_or(b,1);for(int i=0;i<n;i++) a[i]=1ll*a[i]*b[i]%mod;
    fwt_or(a,-1);for(int i=0;i<n;i++) printf("%d ",(a[i]+mod)%mod);puts("");
    // and 
    memcpy(a,ina,sizeof ina);memcpy(b,inb,sizeof inb);
    fwt_and(a,1),fwt_and(b,1);for(int i=0;i<n;i++) a[i]=1ll*a[i]*b[i]%mod;
    fwt_and(a,-1);for(int i=0;i<n;i++) printf("%d ",(a[i]+mod)%mod);puts("");
    // xor
    memcpy(a,ina,sizeof ina);memcpy(b,inb,sizeof inb);
    fwt_xor(a,1),fwt_xor(b,1);for(int i=0;i<n;i++) a[i]=1ll*a[i]*b[i]%mod;
    fwt_xor(a,-1);for(int i=0;i<n;i++) printf("%d ",(a[i]+mod)%mod);puts("");
    return 0;

codeforces662cbinarytable（快速沃尔什变换）(代码片段)

...或一列取反。求最终1的最少个数。Solution前置技能：快速沃尔什变换（FWT）。观察到n较小，考虑(O(2^n))枚举每一行选或不选。不妨设f(x)表示行的操作状态为x时（我们可用一个二进制数表示状态），经过各种列操作后所得到的最... 查看详情

关于快速沃尔什变换（fwt）的一些个人理解(代码片段)

定义FWT是一种快速完成集合卷积运算的算法。它可以用于求解类似C[i]=∑j?k=i A[j]*B[k]的问题。其中?代表位运算中的|，&，^的其中一种。求解（正变换）设F（A）是对于A的一种变换。并且F（A）要求满足： 　　　　 F... 查看详情

洛谷-p4717模板快速莫比乌斯/沃尔什变换(fmt/fwt)(代码片段)

题目链接：点击查看题目分析：看不懂原理我爪巴了代码：//Problem:P4717【模板】快速莫比乌斯/沃尔什变换(FMT/FWT)//Contest:Luogu//URL:https://www.luogu.com.cn/problem/P4717//MemoryLimit:250MB//TimeLimit:1000ms////PoweredbyCPEd 查看详情

hdu5977gardenofeden（树形dp+快速沃尔什变换fwt）(代码片段)

CGZ大佬提醒我，我要是再不更博客可就连一月一更的频率也没有了。。。emmm，正好做了一道有点意思的题，就拿出来充数吧=。=题意一棵树，有$n(nleq50000)$个节点，每个点都有一个颜色，共有$k(kleq10)$种颜色，问有多少条路径可... 查看详情

ntt(代码片段)

...化版——快速数论变换—>优化常数及误差(mFWT)：快速沃尔什变换—>利用类似FFT的东西解决一类卷积 查看详情

2023.4.7模板快速沃尔什变换fwt(代码片段)

2023.4.7【模板】快速沃尔什变换FWT题目概述给定长度为\\(2^n\\)两个序列\\(A,B\\)，设\\(C_i=\\sum_j\\oplusk=iA_j\\timesB_k\\)分别当\\(\\oplus\\)是or,and,xor时求出\\(C\\)我们通常将这个操作，叫做“位运算卷积”，因为它的卷积是按照位运算法则... 查看详情

快速沃尔什变换(代码片段)

快速沃尔什变换题目背景模板题，无背景题目描述给定长度为(2^n)两个序列(A,B)，设(C_i=sum_joplusk=iA_jB_k)分别当(oplus)是or,and,xor时求出(C)输入输出格式输入格式：第一行一个数(n)。第二行(2^n)个数(A_0..A_2^n-1)第三行(2^n)个数(B_0..B_2^n-1)... 查看详情

多项式-快速沃尔什变换(代码片段)

若(·)是一种适用于整数域的二元运算，则两多项式关于此运算的方式定义为(C_k=sum_i·j=kA_i*B_j)，即(C=A·B)。(FWT)主要解决多项式的常见的三种二元位运算，在三种运算下分别构造出不同的变换方式，个人认为比(NTT)简单好背一些。... 查看详情

fwt(代码片段)

(FFT)（快速傅里叶变换）求的是卷积，也就是[C_k=sum_i+j=kA_iB_j]那么(FWT)（快速沃尔什变换）求的就是子集卷积，也就是[C_k=sum_ioplusj=kA_iB_j](oplus)指按位运算(or,and,xor)其实(or,and)卷积应该是(FMT)（快速莫比乌斯变换 查看详情

luogu4717模板快速沃尔什变换（fwt）(代码片段)

　　https://www.cnblogs.com/RabbitHu/p/9182047.html　　完全没有学证明的欲望因为这个实在太好写了而且FFT就算学过也忘得差不多了只会写板子#include<iostream>#include<cstdio>#include<cmath>#include<cstring>#include<cstdlib>#include<... 查看详情

快速沃尔什变换小记(代码片段)

概述(FWT)是用来处理集合卷积的问题。也就是求解(f(n)sumlimits_i|j=nf(i)f(j))类型的问题。其中或运算可以改为(otimes,&)。寻找点值因为总是看不下去那么长的推导，所以每次都是看到一半。然后就在加上自己的一点理解，简单推导... 查看详情

fwt(快速沃尔什变换)

待更。。 查看详情

codeforces662c(快速沃尔什变换fwt)

感觉快速沃尔什变换和快速傅里叶变换有很大的区别啊orz不是很明白为什么位运算也可以叫做卷积（或许不应该叫卷积吧） 我是看 http://blog.csdn.net/liangzhaoyang1/article/details/52819835里的快速沃尔什变换这里说一下自己的理解... 查看详情

p4717模板快速沃尔什变换(代码片段)

$color#0066ff题目描述$给定长度为(2^n)两个序列(A,B)，设(C_i=sum_jopluskA_jB_k)分别当(oplus)是or,and,xor时求出C(color#0066ff输入格式)第一行一个数n。第二行(2^n)个数(A_0..A_2^n-1)第三行(2^n)个数(B_0..B_2^n-1)(color#0066ff输出格式)三行每行(2^n)个数，... 查看详情

快速沃尔什变换模板(代码片段)

inlinevoidFWT_or(ll*f,llx=1)for(intp=2,k=1;p<=n;p<<=1,k<<=1)for(inti=0;i<n;i+=p)for(intj=0;j<k;j++)if(~x)f[i+j+k]=(f[i+j+k]+f[i+j])%P;elsef[i+j+k]=(f[i+j+k]-f[i+j]+P)%P;inlinevoidFWT_and(ll*f,llx=1)for(intp=2,k=1;p<=n;p<<=1,k<<=1)for(inti=0;i<n;i+=p)for(intj=0;... 查看详情

fastwalsh-hadamardtransform——快速沃尔什变换

...一满足交换律的位运算，要求复杂度$O(nlogn)$。 快速沃尔什变换：　　这是什么东西？有用吗？请参阅SDOI2017r2d1-cut。　　看到这个大家是不是立刻想到了快速傅里叶变换？　　$$C_i= 查看详情

fwt快速沃尔什变换学习笔记

FWT快速沃尔什变换学习笔记1、FWT用来干啥啊回忆一下多项式的卷积\(C_k=\sum_i+j=kA_i*B_j\)我们可以用\(FFT\)来做。甚至在一些特殊情况下，我们\(C_k=\sum_i*j=kA_i*B_j\)也能做（SDOI2015序列统计）。但是，如果我们把操作符换一下呢？比如... 查看详情

压缩感知——沃尔什-哈达玛(wht)变换与逆变换的matlab代码实现(代码片段)

沃尔什-哈达玛变换（Walsh-HadmardTransform,WHT），是一种典型的非正弦函数变换，采用正交直角函数作为基函数，具有与傅里叶函数类似的性质，图像数据越是均匀分布，经过沃尔什-哈达玛变换后的数据越... 查看详情