首页 > 其他 > 详细

【模板】线性基

时间:2020-01-24 17:25:46      阅读:75      评论:0      收藏:0      [点我收藏+]

线性基

定义:给定数集\(S\),以异或运算张成的数集与\(Span{S}\)相同的极大线性无关集,称为原数集的一个线性基。
线性基具有以下性质:

  1. 显然,线性基是原数集的一个子集。
  2. 线性基的张成集合中一般不包含有数字0。一般给定的数集中不会有0,否则在线性基中加入0即可。
  3. 张成集合中的每个数都可以唯一表示成基的线性组合。这与第一点是统一的。
  4. 将线性基中的一个元素通过“倍加变换”(在这里即异或上另一个元素),张成集合不变。
  5. 线性基中每一个元素的最高位均不同。

由以上性质不难看出,线性基与线性方程组有一些相似之处。事实上,如果把原数集的每一个元素二进制拆分为多项式,把每一项的系数看作一个向量,将所有系数向量看作一个矩阵的行,那么这个构造出的矩阵就可以看作某个线性方程组的系数矩阵。也就是说,对这个矩阵施以异或意义下的初等行变换,即将某些行消成0行,形成的新矩阵与原矩阵行等价。这给了性质5一个很好的阐释:每个元素的最高位对应的是该系数矩阵化为阶梯形后的主元位置,而主元可以将其他行的该项通过行变换消去,结合异或的性质就不难理解了。
以上基于线性代数的讨论表明,可以使用类似高斯消元的行化简算法求得原数集的一个线性基。把每个行向量压成一个数处理,时间复杂度\(O(n^2)\)

代码:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cctype>
using namespace std;
long long p[70], x;
int n;
void insert(long long x) {
    for (int i = 60; i >= 0; --i) 
        if ((x >> i) & 1) {
            if (!p[i]) {
                p[i] = x; break;
            }
            x ^= p[i];
        }
}
int main() {
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> x, insert(x);
    }
    long long ans = 0;
    for (int i = 60; i >= 0; --i)
        if ((ans ^ p[i]) > ans) ans ^= p[i];
    cout << ans;
    return 0;
}

【模板】线性基

原文:https://www.cnblogs.com/TY02/p/12232383.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!