首页 > 其他分享 >线性基学习笔记

线性基学习笔记

时间：2023-07-29 12:55:10浏览次数：43  
标签：int register 笔记 学习 异或 线性 include lld

线性基简介

线性基是一种擅长处理异或问题的数据结构.设值域为 \([1,N]\) ，就可以用一个长度为 $⌈\log_2{N}⌉ $ 的数组来描述一个线性基。特别地，线性基第\(i\) 位上的数二进制下最高位也为第\(i\)位。

一个线性基满足，对于它所表示的所有数的集合\(S\)，\(S\)中任意多个数异或所得的结果均能表示为线性基中的元素互相异或的结果，即意，线性基能使用异或运算来表示原数集使用异或运算能表示的所有数。运用这个性质，我们可以极大地缩小异或操作所需的查询次数。

插入和判断

我们考虑插入的操作，令插入的数为\(x\)，考虑\(x\)的二进制最高位\(i\)，

  • 若线性基的第\(i\)位为\(0\)，则直接在该位插入\(x\)，退出；

  • 若线性基的第\(i\)位已经有值\(a_i\) ，则\(x = x ⊕ a_i\)，重复以上操作直到\(x=0\)。

如果退出时\(x=0\)，则此时线性基已经可以表示原先的\(x\)了；

反之，则说明为了表示\(x\)，往线性基中加入了一个新元素。

很容易证明这样复杂度为\(\log_2{N}\)，也可以用这种方法判断能否通过原数列异或得到一个数\(x\)。

inline void Insert (register lld x) {
	for (register int i = 63; i >= 0; --i)
		if (x & (1ll << i))
			if (!a[i]) {
				a[i] = x;
				break;
			}
			else  x ^= a[i];
}

inline bool Check (register lld x) {
	for (register int i = 63; i >= 0; --i)
		if (x & (1ll << i))
			if (!a[i])  return false;
			else  x ^= a[i];
	return true;
}

查询异或最值

查询最小值相对比较简单。考虑插入的过程，因为每一次跳转操作，\(x\)的二进制最高位必定单调降低，所以不可能插入两个二进制最高位相同的数。而此时，线性基中最小值异或上其他数，必定会增大。所以，直接输出线性基中的最小值即可。

考虑异或最大值，从高到低遍历线性基，考虑到第\(i\)位时，如果当前的答案\(x\)第\(i\)位为\(0\)，就将\(x\)异或上 $ a_i $ ；否则不做任何操作。显然，每次操作后答案不会变劣，最终的\(x\)即为答案。

同样，我们考虑对于一个数\(x\)，它与原数列中的数异或的最值如何获得。用与序列异或最大值类似的贪心即可解决。

inline lld Query_max () {
	register lld res = 0;
	for (register int i = 63; i >= 0; i --)
		res = max (res, res ^ a[i]);
	return res;
}

inline lld Query_min () {
	if (Check (0))  return 0;
	for (register int i = 0; i <= 63; i ++)
		if (a[i])  return a[i];
}

查询k小值

我们考虑进一步简化线性基。显然，一个线性基肯定可以表示为若干个形如\(2^i\) 的数。从高到低处理线性基每一位，对于每一位向后扫，如果当前数第\(i\)位为\(0\)，且线性基第\(i\)位不为\(0\),则将当前数异或上\(a_i\)。这一操作可以在\(O(\log⁡_2^2{n})\)的时间内解决。

经过这一步操作后，设线性基内共有\(cnt\)个数，则它们共可以表示出\(2^cnt\)个数。当然，对于\(0\)必须特殊考虑。如果插入的总数\(n\)与\(cnt\)相等，就无法表示\(0\)了。

同样，考虑最小值时，也必须要考虑到\(0\)的情况。事实上，如果插入时出现了未被加入的元素，就肯定可以表示出\(0\)。

随后，我们考虑将\(k\)二进制拆分，用与快速幂类似的方法就可以求出第\(k\)大值。

学过线性代数的同学应该可以看出，这个过程就是对一个矩阵求解异或意义下的秩的过程。因此，\(cnt \leqslant \lceil \log_2{N} \rceil\)一定成立。而最终，线性基中保存的也是异或意义下的一组极小线性无关组。

lld tmp[70];
inline lld Query (lld k) {
	register lld res = 0;
	register int cnt = 0;
	k -= Check (0);
	if (!k)  return 0;
	for (register int i = 0; i <= 63; i ++) {
		for (register int j = i - 1; j; j --)
			if (a[i] & (1ll << j))  a[i] ^= a[j];
		if (a[i])  tmp[cnt ++] = a[i];
	}
	if (k >= (1ll << cnt))  return -1;
	for (register int i = 0; i < cnt; i ++)
		if (k & (1ll << i))  res ^= tmp[i];
	return res;
}

[TJOI2008] 彩灯

题目链接 - [TJOI2008] 彩灯

题意

求线性基中有多少个线性无关的向量，输出 \(2^{num}\)。

Solution

线性基模板题。

Code

点击查看代码 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 150;
typedef long long lld;

inline lld read() {
	register lld w = 0, f = 1;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-')  f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		w = w * 10 + c - '0';
		c = getchar();
	}
	return w * f;
}

int n, m, num;
lld a[N];
char s[N];

inline void Insert (register lld x) {
	for (register int i = 52; i >= 0; -- i)
		if (x & (1ll << i))
			if (!a[i]) {
				a[i] = x;
				++ num;
				break;
			}
			else  x ^= a[i];
}

int main() {
	n = read(), m = read();
	for (register int i = 1; i <= m; ++ i) {
		scanf ("%s ", s + 1);
		register lld x = 0;
		for (register int j = 1; j <= n; ++ j)
			if (s[j] == 'O')  x = (x << 1) + 1;
			else  x = x << 1;
		Insert (x);
	}

	register lld ans = 1;
	for (register int i = 1; i <= num; ++ i)  ans = 2ll * ans % 2008;
	printf ("%lld\n", ans);
	return 0;
}

[BJWC2011] 元素

题目链接 - [BJWC2011] 元素

题意

给定若干个元素，每个元素有一个权值和一个贡献，要求选出若干个元素构成集合\(S\)，使得\(S\)的任一子集的异或和不为\(0\)，求最大的贡献。

Solution

我们可以按照贡献排序，然后贪心的尝试将每个元素加入线性基，最终线性基内所有元素的贡献之和即为答案。

Code

点击查看代码 
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <iostream>

using namespace std;

const int N = 1050;
typedef long long lld;

inline lld read() {
	register lld w = 0, f = 1;
	register char c = getchar();
	while (c > '9' || c < '0') {
		if (c == '-')  f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		w = w * 10 + c - '0';
		c = getchar();
	}
	return w * f;
}

int n;
lld ans;
lld a[N], val[N];

inline void Insert (register lld x, register lld w) {
	for (register int i = 63; i >= 0; -- i)
		if (x & (1ll << i))
			if (!a[i]) {
				a[i] = x;
				return ;
			} else  x ^= a[i];
}

inline bool Query (register lld x) {
	for (register int i = 63; i >= 0; i --)
		if (x & (1ll << i))
			if (!a[i])  return false;
			else  x ^= a[i];
	return true;
}

struct Node {
	lld x, w;
} p[N];
inline bool operator < (register Node x, register Node y) {
	return x.w > y.w;
}

int main() {
	n = read();
	for (register int i = 1; i <= n; ++i)  p[i].x = read(), p[i].w = read();
	sort (p + 1, p + 1 + n);
	for (register int i = 1; i <= n; ++ i) {
		register lld x = p[i].x, w = p[i].w;
		if (!Query (x))  Insert (x, w), ans += w;
	}

	printf ("%lld\n", ans);
	return 0;
}

[CQOI2013] 新Nim游戏

题目链接 - [CQOI2013] 新Nim游戏

题意

类似 Nim 游戏，不过游戏的第一轮变成了可以任取任意堆石子，可以不取但是不能取完，两个人各取一次后按照正常的 Nim 游戏进行。

问先手最少可以取走多少个石子后，让先手必胜。

Solution

考虑后手必胜的状态，也就是当剩余石子的某个子集满足异或和为\(0\)的状态。

那么先手必须使剩下的石子不能满足上述条件，也就是选取若干石子，使得他们的的某个子集不满足异或和为\(0\)的状态，显然可以扔到线性基里判断。

对于取走数量最少，也就是线性基内的数量最多，可以参照上一题。

Code

点击查看代码 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long lld;

const int N = 150;

inline int read () {
	register int x = 0, w = 1;
	register char ch = getchar ();
	for (; ch < '0' || ch > '9'; ch = getchar ()) if (ch == '-') w = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar ()) x = x * 10 + ch - '0';
	return x * w;
}

int n;
int a[N], w[N];
inline void Insert (register int x) {
	for (register int i = 31; i >= 0; --i)
		if (x & (1 << i))
			if (!a[i]) {
				a[i] = x;
				break;
			} else  x ^= a[i];
}
inline bool Query (register lld x) {
	for (register int i = 63; i >= 0; i --)
		if (x & (1ll << i))
			if (!a[i])  return false;
			else  x ^= a[i];
	return true;
}

inline bool cmp (register int x, register int y) {
	return x > y;
}

int main () {
	n = read ();
	for (register int i = 1; i <= n; ++ i)  w[i] = read();
	sort (w + 1, w + 1 + n, cmp);
	register lld ans = 0;
	for (register int i = 1; i <= n; i ++)
		if (Query (w[i]))  ans += w[i];
		else  Insert (w[i]);
	printf ("%lld\n", ans);
	return 0;
}

[WC2011] 最大XOR和路径

题目连接 - [WC2011] 最大XOR和路径

题意

考虑一个边权为非负整数的无向连通图，节点编号为\(1\)到\(N\)，试求出一条从\(1\)号节点到\(N\)号节点的路径，使得路径上经过的边的权值的 XOR 和最大。

Solution

显然我们没法枚举\(1~N\)的每一条路，但我们可以将路径拆成两部分，第一部分是环，第二部分是链。

假设我们选择了一条从\(1~N\)的链，当然，它不一定是最优秀的。但是别忘了，我们可以选择一些环来增广这条链。举个例子：

假设\(k\)是连接这条链和某个环的某条路径，那么显然，链和环都将走过一遍，而这条路径\(k\)会被走过两遍（从链到环一遍，从环到链一遍）。根据我们上面的推论，\(k\)对答案的贡献是\(0\)。于是我们发现，我们根本就没有必要算出这条路径\(k\)（反正贡献是\(0\)）

于是我们枚举所有环，将环上异或和扔进线性基，然后用这条链作为初值，求线性基与这条链的最大异或和。

Code

点击查看代码 
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long lld;

const int N = 5e5 + 50;

inline int read () {
	register int x = 0, w = 1;
	register char ch = getchar ();
	for (; ch < '0' || ch > '9'; ch = getchar ()) if (ch == '-') w = -1;
	for (; ch >= '0' && ch <= '9'; ch = getchar ()) x = x * 10 + ch - '0';
	return x * w;
}

int n, m;
lld a[64];
inline void Insert (register lld x) {
	for (register int i = 63; i >= 0; --i)
		if (x & (1ll << i))
			if (!a[i]) {
				a[i] = x;
				break;
			} else  x ^= a[i];
}

inline lld Query (register lld x) {
	register lld res = x;
	for (register int i = 63; i >= 0; i --)
		if ((res ^ a[i]) > res)  res ^= a[i];
	return res;
}

int cnt;
int head[N], to[N << 2], nxt[N << 2];
lld val[N << 2];
inline void Add (register int u, register int v, register lld w) {
	to[++ cnt] = v;
	nxt[cnt] = head[u];
	val[cnt] = w;
	head[u] = cnt;
}

lld det[N];
bool vis[N];
inline void DFS (register int nw, register lld res) {
	det[nw] = res, vis[nw] = 1;
	for (register int i = head[nw]; i; i = nxt[i]) {
		register int y = to[i];
		if (!vis[y])  DFS (y, res ^ val[i]);
		else Insert (res ^ val[i] ^ det[y]);
	}
}

int main () {
	n = read(), m = read();
	for (register int i = 1; i <= m; ++ i) {
		register int u = read(), v = read();
		register lld w;
		scanf ("%lld", &w);
		Add (u, v, w);
		Add (v, u, w);
	}

	DFS (1, 0);

	printf ("%lld\n", Query (det[n]));
	return 0;	
}

后记

最近牛客+Codeforces+Atcoder的比赛实在是有点多，加上最近感觉一直睡不醒，所以说补题效率一直很低，也就没抽出时间来写具体每道题的算法笔记了，只能合并成一篇学习笔记了。

主观来说也是最近有点松懈，趁牛客第四场没什么题可补的情况之下，把之前的线性基的东西复习一下，顺便写成一篇算法笔记，方便以后翻阅复习。

标签：int,register,笔记,学习,异或,线性,include,lld
From： https://www.cnblogs.com/abigjiong/p/17589491.html

相关文章

  • C++ Primer Plus学习笔记
    仅限main函数,如果没有返回语句,编译器会加隐含的返回语句:return0;WIN1064位系统中,sizeof(int)==sizeof(long)==4.C++17之后,新增byte数据类型,在标头<cstddef>中定义,取值范围[0-255],初始化:std::byteb{42};char取值范围[-128,127]原始字符串R"(string)"R"+*(......
  • 解决(几乎)任何机器学习问题(1、建立你的工作环境)
    原作者：AbhishekThakur原文：GitHub-abhishekkrthakur/approachingalmost:Approaching(Almost)AnyMachineLearningProblem1、建立你的工作环境在我们开始编码之前，在你的机器上设置好一切是非常重要的。在本书中，我们将使用Ubuntu18.04和Python3.7.6。如果你是Win......
  • Meta-Transformer 多模态学习的统一框架
    Meta-Transformer是一个用于多模态学习的新框架，用来处理和关联来自多种模态的信息，如自然语言、图像、点云、音频、视频、时间序列和表格数据，虽然各种数据之间存在固有的差距，但是Meta-Transformer利用冻结编码器从共享标记空间的输入数据中提取高级语义特征，不需要配对的多模态训练......
  • 【Linux】Kali Linux 安全学习笔记（1） - Docker Kali 部署与安装软件
    由于最近要做安全方面的工作，经网友们的推荐选定了kalilinux作为实施平台。但vm直装的方式太过麻烦了，本次kalilinux将采用docker镜像的方式进行部署使用。直接使用run运行命令启动rolling镜像，若镜像不存在，docker会自动进行checkout到本地，如下图：dockerrun-itkal......
  • openGauss学习笔记-24 openGauss 简单数据管理-模式匹配操作符
    openGauss学习笔记-24openGauss简单数据管理-模式匹配操作符数据库提供了三种独立的实现模式匹配的方法：SQLLIKE操作符、SIMILARTO操作符和POSIX-风格的正则表达式。除了这些基本的操作符外，还有一些函数可用于提取或替换匹配子串并在匹配位置分离一个串。24.1LIKE描述：判断字......
  • 『学习笔记』fhq-treap
    啥是平衡树这边建议去这里。分裂一般指的是按值分裂，意思就是以树上的BST（二叉搜索树）的值为关键值分裂。一般会给一个关键值\(val\)，把一棵平衡树分裂成BST值\(\leqval\)和\(>val\)的两部分。主要思想从根开始递归，递归到某一节点，如果当前根节点的BST值小于等于你给的那......
  • 【笔记】构造题
    听说多做构造题长脑子，至少能让我从机械性的考试里清醒一点吧递归子问题剔除问题边缘例题......
  • Unity学习
    Unity学习1常用快捷键alt+鼠标左键：以某个物体为中心旋转视角鼠标左键+w/s/a/d：视角移动F：相机聚焦物体Q/W/E/R/T/Y：左上角工具栏工具2文件资源2.1工程目录Assets目录：主要存放资源文件，该文件中的内容会在unity项目栏中显示。2.2文件类型FBX文件：3D模型文件，其中包括了......
  • 学习IDA权威指南-交叉引用
    使用IDA工具可以直观的提现代码与数据之间的关系。交叉引用一般使用xref表示1-代码交叉引用p-调用流j-跳转流2-数据交叉引用0-代表偏移地址引用r-读取引用w-写入引用3-交叉引用列表鼠标悬停，会出现引用的地方快捷键Ctrl+X函数列表......
  • python学习难点及举例
    在Python的高级学习中，可能会遇到以下几个难点：迭代器和生成器：迭代器和生成器是Python中强大的概念，但在理解和使用它们时可能会有一些困难。迭代器是一种可以遍历数据集合的对象，而生成器是一种特殊的迭代器，可以按需生成值，而不是一次性生成所有值。#迭代器示例my_list=[1,2,3]m......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99