WIKIOI
wiki(I:)
比赛相关
工具软件
语言基础
算法基础
搜索
动态规划
字符串
数学
数据结构
图论
计算几何
杂项
专题
数学部分简介
符号
复数
位运算
快速幂
进位制
高精度计算
平衡三进制
素数
最大公约数
欧拉函数
筛法
欧拉定理 & 费马小定理
类欧几里德算法
裴蜀定理
乘法逆元
线性同余方程
中国剩余定理
二次剩余
BSGS
原根
卢卡斯定理
莫比乌斯反演
杜教筛
Min_25 筛
分解质因数
多项式部分简介
拉格朗日插值
快速傅里叶变换
快速数论变换
快速沃尔什变换
多项式求逆
多项式开方
多项式除法|取模
多项式对数函数|指数函数
多项式牛顿迭代
多项式多点求值|快速插值
多项式三角函数
多项式反三角函数
常系数齐次线性递推
生成函数简介
普通生成函数
指数生成函数
向量
矩阵
高斯消元
线性基
线性规划简介
单纯形算法
排列组合
卡特兰数
斯特林数
贝尔数
伯努利数
康托展开
容斥原理
抽屉原理
概率初步
置换群
斐波那契数列
博弈论
牛顿迭代法
数值积分
分段打表
64 objects
本站非官方,所收集资源均来源于网络。
线性基 - 数学
线性基是向量空间的一组基,通常可以解决有关异或的一些题目。 通俗一点的讲法就是由一个集合构造出来的另一个集合,它有以下几个性质: - 线性基的元素能相互异或得到原集合的元素的所有相互异或得到的值。 - 线性基是满足性质 1 的最小的集合。 - 线性基没有异或和为 0 的子集。 - 线性基中每个元素的异或方案唯一,也就是说,线性基中不同的异或组合异或出的数都是不一样的。 - 线性基中每个元素的二进制最高位互不相同。 构造线性基的方法如下: 对原集合的每个数 p 转为二进制,从高位向低位扫,对于第 $x$ 位是 1 的,如果 $a_x$ 不存在,那么令 $a_x=p$ 并结束扫描,如果存在,令 $p=p~\text{xor}~a_x$ 。 代码: ```cpp inline void insert(long long x) { for (int i = 55; i + 1; i--) { if (!(x >> i)) // x的第i位是0 continue; if (!p[i]) { p[i] = x; break; } x ^= p[i]; } } ``` 查询原集合内任意几个元素 xor 的最大值,就可以用线性基解决。 将线性基从高位向低位扫,若 xor 上当前扫到的 $a_x$ 答案变大,就把答案异或上 $a_x$ 。 为什么能行呢?因为从高往低位扫,若当前扫到第 $i$ 位,意味着可以保证答案的第 $i$ 位为 1,且后面没有机会改变第 $i$ 位。 查询原集合内任意几个元素 xor 的最小值,就是线性基集合所有元素中最小的那个。 查询某个数是否能被异或出来,类似于插入,如果最后插入的数 $p$ 被异或成了 0,则能被异或出来。 ## 线性基练习题 [SGU 275 to xor or not xor](https://vjudge.net/problem/SGU-275) [HDU 3949 XOR](https://loj.ac/problem/161) [Luogu P4151\[WC2011\]最大 XOR 和路径](https://www.luogu.com.cn/problem/P4151)