首页 > 其他分享 >位运算卷积学习笔记

位运算卷积学习笔记

时间：2024-07-30 19:42:13浏览次数：15  
标签：运算 卷积 text sum 笔记 circ int FWT FMT

位运算卷积学习笔记

位运算卷积，即快速沃尔什变换 \(\text{FWT}\) 和快速莫比乌斯变换 \(\text{FMT}\)，但事实上最常用的是 \(\text{FWT}\)，因为 \(\text{FMT}\) 所求解的内容是 \(\text{FWT}\) 的子集。

位运算卷积

首先要知道位运算卷积指的是

\[c_i=\sum_{j\odot k=i}a_jb_k \]

形式的式子，其中 \(\odot\) 代指了任意位运算符，也就是 \(\text{or},\text{and},\text{xor}\)。利用 \(\text{FMT}\) 能够求解 \(\text{or},\text{and}\) 卷积，而利用 \(\text{FWT}\) 能够求解 \(\text{or},\text{and},\text{xor}\) 卷积。

快速莫比乌斯变换

\(\text{or}\) 卷积

先考虑暴力求解的时间复杂度是 \(O(n^2)\) 的，不妨考虑和 \(\text{FFT}\) 相同的思路，找到一个 \(\text{FMT}(a)\) 满足 \(\text{FMT}(c)_i=\text{FMT}(a)_i\times\text{FMT}(b)_i\)，这样我们便可以通过顺逆变换快速求出 \(c\)。

定义 \(\text{FMT}(a)_i=\sum_{j\cup i=i}a_j\)，其中 \(\cup\) 表示按位或，而这种构造显然符合要求，因为有

\[\begin{aligned}\text{FMT}(a)_i\times\text{FMT}(b)_i&=\sum_{j\cup i=i}a_j\sum_{k\cup i=i}b_k\\&=\sum_{(j\cup k)\cup i=i}a_jb_k\\&=\text{FMT}(c)_i \end{aligned} \]

由此我们得到了一个构造，而且不难发现这其实就是 \(a\) 的高维前缀和，按照前缀和的思路将 \(n\) 维二进制看作 \(n\) 维数组求解前缀和即可。而对于逆变换只需要进行差分即可。时间复杂度是 \(O(n\log n)\) 的。

代码

int n;
int A[1<<n],B[1<<n],C[1<<n];

void FMT_OR(int n,int *a,int type){
	for(int i=0;i<n;i++){
		for(int j=0;j<(1<<n);j++){
			if(j&(1<<i))a[j]+=type*a[j^(1<<i)];
		}
	}
	return ;
}

int main(){
	cin>>n;
	for(int i=0;i<(1<<n);i++)cin>>A[i];
	for(int i=0;i<(1<<n);i++)cin>>B[i];
	FMT_OR(n,A,1);
	FMT_OR(n,B,1);
	for(int i=0;i<(1<<n);i++)C[i]=A[i]*B[i];
	FMT_OR(n,C,-1);
	for(int i=0;i<(1<<n);i++)cout<<C[i]<<" ";
	return 0;
}

\(\text{and}\) 卷积

和 \(\text{or}\) 卷积同理，考虑构造一个 \(\text{FMT}(a)_i\)，在这里定义 \(\text{FMT}(a)_i=\sum_{j\cap i=i}a_j\)，\(\cap\) 表示按位与，那么有

\[\begin{aligned}\text{FMT}(a)_i\times \text{FMT}(b)_i&=\sum_{j\cap i=i}a_j\sum_{k\cap i=i}b_k\\&=\sum_{(j\cap k)\cap i=i}a_jb_k\\&=\text{FMT}(c)_i \end{aligned} \]

于是考虑如何求解 \(\text{FMT}(a)_i\)，发现其为高位后缀和的形式，于是有复杂度 \(O(n\log n)\)。

代码

int n;
int A[1<<n],B[1<<n],C[1<<n];

void FMT_AND(int n,int *a,int type){
	for(int i=0;i<n;i++){
		for(int j=0;j<(1<<n);j++){
			if(j&(1<<i))a[j^(1<<i)]+=type*a[j];
		}
	}
	return ;
}

int main(){
	cin>>n;
	for(int i=0;i<(1<<n);i++)cin>>A[i];
	for(int i=0;i<(1<<n);i++)cin>>B[i];
	FMT_AND(n,A,1);
	FMT_AND(n,B,1);
	for(int i=0;i<(1<<n);i++)C[i]=A[i]*B[i];
	FMT_AND(n,C,-1);
	for(int i=0;i<(1<<n);i++)cout<<C[i]<<" ";
	return 0;
}

快速沃尔什变换

\(\text{or}\) 变换

其实有关于 \(\text{or},\text{and}\) 的 \(\text{FWT}\) 和 \(\text{FMT}\) 的构造完全相同，只是求解的方法不同而已，我们在这里考虑分治的做法，也就是更接近 \(\text{FFT}\) 的做法。依旧构造 \(\text{FWT}(a)_i=\sum_{j\cup i=i}a_j\)，正确性不加复述，下面考虑分治。对于分治序列 \(\text{FWT}(a)\) 的第 \(i\) 位，我们将其分为两部分 \(\text{FWT}(a)_0,\text{FWT}(a)_1\)，分别表示在 \(i-1\) 位分治后序列左半部分和右半部分，于是有

\[\text{FWT}(a)=\text{merge}(\text{FWT}(a)_0,\text{FWT}(a)_0+\text{FWT}(a)_1) \]

这个正确性是显然的，因为对于 \(\text{FWT}(a)_0\) 来说，其分治位置上均为 \(0\)，所需要累加的对应位置 \(j\) 若要满足 \(j\cup i=i\) 则其当前分治位也需为 \(0\)。而对于 \(\text{FWT}(a)_1\) 来说，\(j\) 的当前分治位即可以为 \(1\)，也可以为 \(0\)，因此只需要将后半段加上前半段即可。

关于逆变换则恰相反，只需要将前半段对后半段的贡献消去即可，也就是在后半段减去前半段。也就是

\[a=\text{merge}(a_0,a_1-a_0) \]

代码

int n;
int A[1<<n],B[1<<n],C[1<<n];

void FWT_OR(int n,int *a,int type){
	for(int len=1;len<n;len<<=1){
		for(int l=0;l<n;l+=(len<<1)){
			for(int k=0;k<len;k++)a[l+len+k]+=type*a[l+k];
		}
	}
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=0;i<(1<<n);i++)cin>>A[i];
	for(int i=0;i<(1<<n);i++)cin>>B[i];
	FWT_OR(1<<n,A,1);
	FWT_OR(1<<n,B,1);
	for(int i=0;i<(1<<n);i++)C[i]=A[i]*B[i];
	FWT_OR(1<<n,C,-1);
	for(int i=0;i<(1<<n);i++)cout<<C[i]<<" ";
	return 0;
}

\(\text{and}\) 卷积

依旧同理有 \(\text{FWT}(a)_i=\sum_{j\cap i=i}a_j\)，正确性不加复述，考虑分治的做法。对于分治序列 \(\text{FWT}(a)\) 的第 \(i\) 位，我们将其分为两部分 \(\text{FWT}(a)_0,\text{FWT}(a)_1\)，分别表示在 \(i-1\) 位分治后序列左半部分和右半部分，于是有

\[\text{FWT}(a)=\text{merge}(\text{FWT}(a)_0+\text{FWT}(a)_1,\text{FWT}(a)_1) \]

同理，当第 \(i\) 位为 \(0\) 时，\(j\) 的当前分治位即可以是 \(0\) 也可以是 \(1\)，而当第 \(i\) 位为 \(1\) 时，\(j\) 的当前分治位只能是 \(1\)，逆变换同理减回去即可。

\[a=\text{merge}(a_0-a_1,a_1) \]

代码

int n;
int A[1<<n],B[1<<n],C[1<<n];

void FWT_AND(int n,int *a,int type){
	for(int len=1;len<n;len<<=1){
		for(int l=0;l<n;l+=(len<<1)){
			for(int k=0;k<len;k++)a[l+k]+=type*a[l+len+k];
		}
	}
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=0;i<(1<<n);i++)cin>>A[i];
	for(int i=0;i<(1<<n);i++)cin>>B[i];
	FWT_AND(1<<n,A,1);
	FWT_AND(1<<n,B,1);
	for(int i=0;i<(1<<n);i++)C[i]=A[i]*B[i];
	FWT_AND(1<<n,C,-1);
	for(int i=0;i<(1<<n);i++)cout<<C[i]<<" ";
	return 0;
}

\(\text{xor}\) 卷积

引入一个新的运算符 \(\circ\)。定义 \(x\circ y=\text{popcnt}(x\cap y)\bmod 2\)，其中 \(\text{popcnt}(x)\) 表示 \(x\) 二进制下 \(1\) 的个数。我们发现它满足 \((x\circ y)\oplus(x\circ z)=x\circ (y\oplus z)\)。

更感性的理解，\(x\circ y\) 表示 \(x,y\) 均为 \(1\) 位数的奇偶性。对于每一位的 \(x,y,z\)，可以列出下表

\(x\) \(y\) \(z\) \(y\oplus z\) \(x\circ y\) \(x\circ z\) \(x\circ (y\oplus z)\)
\(0\) \(0\) \(0\) \(0\) \(0\) \(0\) \(0\)
\(0\) \(0\) \(1\) \(1\) \(0\) \(0\) \(0\)
\(0\) \(1\) \(0\) \(1\) \(0\) \(0\) \(0\)
\(0\) \(1\) \(1\) \(0\) \(0\) \(0\) \(0\)
\(1\) \(0\) \(0\) \(0\) \(0\) \(0\) \(0\)
\(1\) \(0\) \(1\) \(1\) \(0\) \(1\) \(1\)
\(1\) \(1\) \(0\) \(1\) \(1\) \(0\) \(1\)
\(1\) \(1\) \(1\) \(0\) \(1\) \(1\) \(0\)

不难看出，不管 \(x,y,z\) 的每一位如何变化，对应位对答案贡献的奇偶性始终不变，故上式成立。

由此，设 \(\text{FWT}(a)_i=\sum_{j\circ i=0}a_j-\sum_{j\circ i=1}a_j\)。则有

\[\begin{aligned}\text{FWT}(a)_i\times\text{FWT}(b)_i&=(\sum_{j\circ i=0}a_j-\sum_{j\circ i=1}a_j)(\sum_{j\circ i=0}b_j-\sum_{j\circ i=1}b_j)\\&=(\sum_{j\circ i=0}a_j\sum_{k\circ i=0}b_k+\sum_{j\circ i=1}a_j\sum_{k\circ i=1}b_k)-(\sum_{j\circ i=0}a_j\sum_{k\circ i=1}b_k+\sum_{j\circ i=1}a_j\sum_{k\circ i=0}b_k)\\&=\sum_{(j\oplus k)\circ i=0}a_jb_k-\sum_{(j\oplus k)\circ i=1}a_jb_k\\&=\text{FWT}(c)_i \end{aligned} \]

由此，该构造的正确性得证，接着考虑如何分治求解。当前位 \(i\) 为 \(0\) 时，不论 \(j\) 取 \(0,1\)，\(i\circ j\) 均为 \(0\)，那么 \(\text{FWT}(a)_0,\text{FWT}(a)_1\) 对该位的贡献均为正，而当 \(i\) 为 \(1\) 时，如果 \(j\) 取 \(0\)，则对答案没有影响，但若取 \(1\)，则应对原贡献取负。即

\[\text{FWT}(a)=\text{merge}(\text{FWT}(a)_0+\text{FWT}(a)_1,\text{FWT}(a)_0-\text{FWT}(a)_1) \]

而在逆变换时有

\[a=\text{merge}(\frac{a_0+a_1}{2},\frac{a_0-a_1}{2}) \]

于是对于传参稍作改动，逆变换时 \(\text{type}\) 取 \(\frac{1}{2}\)。

代码

int n;
int A[1<<n],B[1<<n],C[1<<n];

void FWT_XOR(int n,int *a,int type){
	for(int len=1;len<n;len<<=1){
		for(int l=0;l<n;l+=(len<<1)){
			for(int k=0;k<len;k++){
				ll A=a[l+k],B=a[l+len+k];
				a[l+k]=(A+B)/type;
				a[l+len+k]=(A-B)/type;
			}
		}
	}
	return ;
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>n;
	for(int i=0;i<(1<<n);i++)cin>>A[i];
	for(int i=0;i<(1<<n);i++)cin>>B[i];
	FWT_XOR(1<<n,A,1);
	FWT_XOR(1<<n,B,1);
	for(int i=0;i<(1<<n);i++)C[i]=A[i]*B[i];
	FWT_XOR(1<<n,C,2);
	for(int i=0;i<(1<<n);i++)cout<<C[i]<<" ";
	return 0;
}

标签：运算,卷积,text,sum,笔记,circ,int,FWT,FMT
From： https://www.cnblogs.com/DycBlog/p/18333220

相关文章

  • 【调试笔记-20240730-Linux-OpenWrt 23.05 安装 Docker 配置 bitnami/Wordpress-with-
    调试笔记-系列文章目录调试笔记-20240730-Linux-OpenWrt23.05安装Docker配置bitnami/Wordpress-with-NGINX实现微信用户在线注册登录文章目录调试笔记-系列文章目录调试笔记-20240730-Linux-OpenWrt23.05安装Docker配置bitnami/Wordpress-with-NGINX实现......
  • ssy中学暑假集训分数规划笔记
    分数规划出现在了我们今天的模拟赛中，看在这个名字深得我心而且我能看懂证明和内容的份上，给开个专题吧！\(1.定义\)：分数规划就是求分数的极值。形象一点就是，给出\(a_i\)和\(b_i\)，求一组\(w_i\in\{0,1\}\)最小化或者最大化下面的算式：\[\frac{\sum_{i=1}^{n}a_i*w_i}{\sum_{i=1}......
  • c语言第七天笔记
    作业题：设计TVM（地铁自动售票机）机软件。输入站数，计算费用，计费规则，6站2元，7-10站3元，11站以上为4元。输入钱数，计算找零(找零时优先找回面额大的钞票)，找零方式为各种面额张数，可识别面额：100,50,20,10,5,1案例代码：运行效果：循环结构什么是循环代码的重复执行，就叫做循环。循......
  • Electron学习笔记（二）Hello World
    目录前言运行主进程创建界面使用窗口打开界面管理窗口的生命周期关闭所有窗口时退出应用(Windows&Linux)​如果没有窗口打开则打开一个窗口(macOS)使用预加载脚本访问渲染器的Node.js添加你自己的功能完整代码展示效果展示前言接上一篇文章Electron学习笔......
  • 笔记：从Aurora 8b/10b 到Aurora 64b/66b (一)：Aurora 8b/10b
    参考：https://www.xilinx.com/products/intellectual-property/aurora8b10b.html#documentationhttps://docs.amd.com/r/en-US/pg046-aurora-8b10bhttps://docs.amd.com/v/u/en-US/aurora_8b10b_ds797https://mp.weixin.qq.com/s/gT4QUgvoFF6UI0PAhfEPvQ补丁：Aurora系IP内部......
  • 虚树【学习笔记】
    为什么要用虚树？例题在某些树上问题中，对于某次询问，我们并不需要用到全部的树上的点：例如，例题中：总点数\(n\le2.5\times10^5\)询问次数\(m\le5\times10^5\)询问的点数\(\sumk_i\le5\times10^5\)我们可以发现其实每次询问均摊下来的询问点数k并不多，但如果每次询问都......
  • Python基础知识笔记---保留字
    保留字，也称关键字，是指被编程语言内部定义并保留使用的标识符。一、保留字概览  二、保留字用途 1.`False`：表示布尔值假。2.`None`：表示空值或无值。3.`True`：表示布尔值真。4.`not`：布尔逻辑操作符，对条件表达式取反。5.`or`：布尔逻辑操作符，用于连接两个条件表达式......
  • 【笔记】图论：2-sat、连通性、欧拉回路选讲
    [AGC059C]GuessingPermutationforasLongasPossible（2-sat）这个东西十分智障，只需要对于所有\(a,b,c\)，如果询问顺序是\((a,b),(b,c),(a,c)\)，那么不能\(a<b<c\)或\(a>b>c\)。其它的情况（一条链）你一看发现肯定需要出现上述情况，那么这就是充要条件。你一看你直接对所......
  • [rCore学习笔记 019]在main中测试本章实现
    写在前面本随笔是非常菜的菜鸡写的。如有问题请及时提出。可以联系：[email protected]：https://github.com/WindDevil（目前啥也没有批处理操作系统的启动和运行流程要想把本章实现的那些模块全部都串联在一起以实现运行一个批处理操作系统,回顾本章内容,思考批处理操作......
  • x264 环路滤波原理系列：滤波运算函数
    x264滤波运算函数关系图滤波强度Bs=1、2、3的滤波运算相关函数deblock_luma_c函数原理逻辑过程：for循环处理MB中每个4x4的块；如果tc0[i]小于0，表示当前行不需要去块处理，函数将跳过当前行，通过continue跳转到下一次迭代。for循环遍历4x4块边的像素点；......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99