来源

强烈推荐这篇文章，以下内容大部分来自于此。

前言

这篇是根据以上的博客再结合自己的浅薄理解写的，讲得并不详细，因为弱鸡本人还没完全懂，先学会使用吧。

概述

首先所谓的线性基，就是把若干个整数，看成 n 维 01 向量（通常 n 不会超过 64，即 long long 的范围），然后求这些向量的一个极大无关组。需要注意的一点是，对于这里的 01 向量，只有异或运算。

下面是利用高斯消元求解线性基的代码

void cal() {//a[i]为原来的数，b[i]为新的向量    for (int i = 0; i < n; ++i)        for (int j = MAX_BASE; j >= 0; --j)            if (a[i] >> j & 1) {                if (b[j]) a[i] ^= b[j];                else {                    b[j] = a[i];                    for (int k = j - 1; k >= 0; --k) if (b[k] && (b[j] >> k & 1)) b[j] ^= b[k];                    for (int k = j + 1; k <= MAX_BASE; ++k) if (b[k] >> j & 1) b[k] ^= b[j];                    break;                }}

对于最后得到的矩阵，如果第

例题

SGU - 275

给定

#include 
     
      using namespace std;typedef long long ll;const int MAX_BASE = 63;ll b[200];ll a[11234];void cal(int n) {    for (int i = 0; i < n; i++) {        for (int j = MAX_BASE; j >= 0; j--) {            if (a[i] >> j & 1) {                if (b[j]) a[i] ^= b[j];                else {                    b[j] = a[i];                    for (int k = j - 1; k >= 0; k--) if (b[k] && b[j] >> k & 1) b[j] ^= b[k];                    for (int k = j + 1; k <= MAX_BASE; k++) if (b[k] >> j & 1) b[k] ^= b[j];                    break;                }            }        }    }}int main() {    int n;    while (~scanf("%d", &n)) {        memset(b, 0, sizeof(b));        for (int i = 0; i < n; i++) {            scanf("%lld", a + i);        }        cal(n);        ll ans = 0;        for (int i = 0; i <= MAX_BASE; i++) {            if (b[i] >> i & 1) ans ^= b[i];        }        printf("%lld\n", ans);    }}

HDU - 3949

给定

分析

我们求出向量空间 $2^∣B∣−1，特别的，如果 ∣B∣<n，则必然存在一个向量组满足线性相关性，这个向量组也就能通过线性组合，异或得到 0，则异或和的个数为 2^∣B∣。$

假设线性基中有

//  Created by Sengxian on 2016/12/5.//  Copyright (c) 2016年 Sengxian. All rights reserved.//  HDOJ 3949 线性基#include 
     
      using namespace std;typedef long long ll;inline ll readLL() {    static ll n;    static int ch;    n = 0, ch = getchar();    while (!isdigit(ch)) ch = getchar();    while (isdigit(ch)) n = n * 10 + ch - '0', ch = getchar();    return n;}const int MAX_N = 100000 + 3, MAX_BASE = 60;int n, zero = false;ll a[MAX_N], b[MAX_BASE + 3];vector
      
        mmap;void prepare() {    int cnt = 0;    memset(b, 0, sizeof b);    for (int i = 0; i < n; ++i)        for (int j = MAX_BASE; j >= 0; --j)            if (a[i] >> j & 1) {                if (b[j]) a[i] ^= b[j];                else {                    b[j] = a[i], cnt++;                    for (int k = j - 1; k >= 0; --k) if (b[k] && ((b[j] >> k) & 1)) b[j] ^= b[k];                    for (int k = j + 1; k <= MAX_BASE; ++k) if ((b[k] >> j) & 1) b[k] ^= b[j];                    break;                }            }    zero = cnt != n;    mmap.clear();    for (int i = 0; i <= MAX_BASE; ++i)        if (b[i]) mmap.push_back(b[i]);}ll query(ll k) {    if (zero) k--;    if (k >= (1LL << (int)mmap.size())) return -1;    ll ans = 0;    for (int i = 0; i < (int)mmap.size(); ++i) if ((k >> i) & 1)        ans ^= mmap[i];    return ans;}int main() {#ifdef DEBUG    freopen("test.in", "r", stdin);#endif    int caseNum = readLL();    for (int t = 1; t <= caseNum; ++t) {        n = readLL();        for (int i = 0; i < n; ++i) a[i] = readLL();        prepare();        printf("Case #%d:\n", t);        int q = readLL();        for (int i = 0; i < q; ++i) printf("%lld\n", query(readLL()));    }    return 0;}

小结

线性基的题型相对比较固定，看到下面的类型基本上都是线性基了：

最大异或和

求所有异或值的和

转载于:https://www.cnblogs.com/fht-litost/p/9562807.html

你可能感兴趣的文章