WIKI

线性基

我们知道 不同的两个数 异或的结果有可能相同

对于一组 组合中， 存在不同的 组合的异或的结果是 相同的 ，根据这个性质 我们引入 线性基

把$n$个 数的组合 求 异或 缩小到 $m$ 个数(线性基)的组合 求异或

线性基的性质

1. 等价性
2. 最小性 ， $P$ 是满足 (1) 中 元素最少的
3. $P$ 中 不存在 异或结果为0的 子集 (P中不存在， A中可能存在)

线性基的构造

code

#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
constexpr int M = 63;
int p[M];
bool zero;
void insert(int x) {
  for (int i = M; i >= 0; i--) {
    if ((x >> i) & 1) {
      if (p[i] == 0) {
        p[i] = x;
        return;
      } else
        x ^= p[i];
    }
  }
  zero = true;
}
int qmax() {
  int ans = 0;
  for (int i = M; ~i; i--) ans = max(ans, ans ^ p[i]);
  return ans;
}
void solve() {
  cin >> n;
  vector<int> a(n);
  for (auto &i : a) {
    cin >> i;
    insert(i);
  }
  cout << qmax() << "\n";
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  solve();
  return 0;
}

TJOI2008 彩灯

Peter 女朋友的生日快到了，他亲自设计了一组彩灯，想给女朋友一个惊喜。已知一组彩灯是由一排 $N$ 个独立的灯泡构成的，并且有 $M$ 个开关控制它们。从数学的角度看，这一排彩灯的任何一个彩灯只有亮与不亮两个状态，所以共有 $2^N$ 个样式。由于技术上的问题，Peter 设计的每个开关控制的彩灯没有什么规律，当一个开关被按下的时候，它会把所有它控制的彩灯改变状态（即亮变成不亮，不亮变成亮）。假如告诉你他设计的每个开关所控制的彩灯范围，你能否帮他计算出这些彩灯有多少种样式可以展示给他的女朋友？

注： 开始时所有彩灯都是不亮的状态。

每组测试数据第一行为两个整数 $N$ 和 $M$，用空格隔开。紧接着是有 $M$ 行，每行都是一个长度为 $N$ 的字符串，表示一个开关控制彩灯的范围（$N$ 盏灯），如果第 $i$ 个字母是大写字母 O，则表示这个开关控制第 $i$ 盏灯，如果第 $i$ 个字母是大写字母 X，则表示这个开关不控制此灯。

输出这些开关和彩灯可以变换出来的样式数目。由于这个值可能会很大，请求出它对于整数 $2008$ 的余数。

可见样例中第一个开关控制了所有的彩灯，而后两个开关分别控制了第一个和第二个彩灯，这样我们可以只用后两个开关控制彩灯，可以变换出来所有的 $2^2$ 个状态。

对于 $30\%$ 的数据，$N$ 和 $M$ 不超过 $15$。

另外有 $40\%$ 的数据，$N$ 和 $M$ 有一个为 $50$。

对于 $100\%$ 的数据，$N$ 和 $M$ 不超过 $50$。

code

// Luogu P3857 [TJOI2008] 彩灯
// https://www.luogu.com.cn/problem/P3857 2024-03-13 14:58:30

#include <bits/stdc++.h>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, m;
constexpr int M = 63;
int p[M], cnt;
void insert(int x) {
  for (int i = M; ~i; i--) {
    if ((x >> i) & 1) {
      if (p[i]) {
        x ^= p[i];
      } else {
        cnt++;
        return (void)(p[i] = x);
      }
    }
  }
}
void solve() {
  cin >> n >> m;
  for (int i = 0; i < m; i++) {
    string s;
    cin >> s;
    int res = 0;
    for (auto it : s) {
      if (it == 'O') {
        res = res << 1;
      } else
        res = res << 1 | 1;
    }
    insert(res);
  }
  cout << (1LL << cnt) % 2008 << "\n";
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  solve();
  return 0;
}

异或线性基求k大

Problem - 3949 (hdu.edu.cn)

code

// HDOJ XOR
// https://acm.hdu.edu.cn/showproblem.php?pid=3949 2024-03-13 15:04:17

#include <iostream>
using namespace std;
#define all(a) begin(a), end(a)
#define int long long
int n, q, cnt;
bool zero;
const int N = 1E4 + 10;
int a[N];
void Gauss() {
  int i, k = 1;
  int j = (1LL << 62);
  for (; j; j >>= 1) {
    for (i = k; i <= n; i++) {
      if (a[i] & j) break;
    }
    if (i > n) continue;
    swap(a[i], a[k]);
    for (i = 1; i <= n; i++)
      if ((i != k) && (a[i] & j)) a[i] ^= a[k];
    k++;
  }
  k--;
  if (k == n)
    zero = false;
  else
    zero = true;
  n = k;
}
int query(int k) {
  int ans = 0;
  if (zero) k--;
  if (!k)
    return 0;
  else {
    for (int i = n; i; i--) {
      if (k & 1) ans ^= a[i];
      k >>= 1;
    }
    if (k)
      return -1;
    else
      return ans;
  }
}
void solve() {
  cin >> n;
  for (int i = 1; i <= n; i++) cin >> a[i];
  Gauss();
  cin >> q;
  while (q--) {
    int x;
    cin >> x;
    cout << query(x) << "\n";
  }
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(0), cout.tie(0);
  int __;
  cin >> __;
  while (__--) {
    cout << "Case #" << (++cnt) << ":\n";
    solve();
  }
  return 0;
}