[学习笔记] 线性基

RB16B / 2023-08-16 / 原文

~~你说我一个连线性基都不会的人怎么可能走的远，我跟你说我也是这么想的，但是你先别急。~~

一、线性基

OI 中常用全部的就是 \(2\) 进制下的异或线性基。

线性基就是可以把一个集合里的数转化成一组基，使得这组基里所有 xor 出来的结果于原集合 xor 出来的结果完全一致。

这是一个线性基模板：

struct linear_basis_awa {
  // If don't use "query_kth",
  // please "//" cy[64], bt[64], build_kth(), query_kth(k) and upd thanks meow!
  ll bs[64], cy[64], bt[64];
  int cnt, upd, num;
  inline void init () {
    upd = 1;
    for (int i = 0;i < 64; ++ i) bs[i] = 0;
    cnt = 0;
  }
  inline void ins (ll x) {
    if (!x) return ;
    upd = 1;
    for (int i = 62;i >= 0; -- i) {
      if (x & (1ll << i)) {
        if (bs[i]) x ^= bs[i];
        else {
          cnt ++;
          bs[i] = x;
          break;
        }
      }
    }
  }
  inline ll query_maxxor (ll x) {
    ll res = x;
    for (int i = 62;i >= 0; -- i) {
      if ((res ^ bs[i]) > res) res ^= bs[i];
    }
    return res;
  }
  inline void merge_bas (linear_basis_awa O) {
    for (int i = 0;i < 64; ++ i) ins (O.bs[i]);
  }
  inline void operator = (linear_basis_awa O) {
    for (int i = 0;i < 64; ++ i) bs[i] = O.bs[i];
    for (int i = 0;i < 64; ++ i) cy[i] = O.cy[i];
    upd = O.upd;
    cnt = O.cnt;
  }
  inline void build_kth () {
    upd = 0;
    for (int i = 0;i < 64; ++ i) cy[i] = bs[i], bt[i] = 0;
    for (int i = 62;i >= 0; -- i) {
      for (int j = i - 1;j >= 0; -- j) {
        if (cy[i] & (1ll << j)) cy[i] ^= cy[j];
      }
    }
    num = 0;
    for (int i = 0;i <= 62; ++ i) {
      if (cy[i]) bt[num ++] = cy[i];
    }
  }
  inline ll query_kth (ll k) {
    if (k == 1) return 0;
    k --;
    if (upd) build_kth ();
    if ((1ll << num) < k) return -1ll;
    ll ans = 0;
    for (int i = 0;i <= 62; ++ i) {
      if (k & (1ll << i)) {
        ans ^= bt[i];
      }
    }
    return ans;
  }
};

其中这里的 \(bs_{w}\) 是最高位为 \(2^w\) 的基向量。

线性基的插入

如果 \(x\) 这个数内包含 \(2^w\) 这一位，如果基中已经有，那么直接异或掉 \(2^w\)，否则那就直接加入 \(x\)，然后结束，时间复杂度 \(O(\log w)\)。

线性基求最大 xor 和

对于 query_maxxor (int v) 函数的解释：查询 \(\displaystyle \max_{S \subseteq \text{base}} \left[\left(\bigoplus_{x \in S} x\right) \oplus v\right]\)；做法：贪心，如果 \(2^x\) 这一位异或下来是 \(1\)，那么一定要比后面所有位都是 \(1\) 产生的贡献之和（\(2^x - 1\)）还要大，所以我们从高位往低位贪心肯定是最优的，时间复杂度 \(O(\log w)\)。

线性基 xor 值计数

因为线性基里的数都是线性无关的，所以任意一个子集（不含 \(0\)）xor 出来的值都互不相同，如果含 \(0\) 总共就是 \(2^{cnt}\) 种情况，其中 \(cnt\) 是基中非 \(0\) 的数的数量。

线性基合并

直接将一个线性基里的数暴力插入到另一个线性基里即可，时间复杂度 \(O(\log^2 w)\)。

线性基求第 \(k\) 小 xor 值

首先说一下，这个第 \(k\) 小是 去重后，含 \(\textbf{0}\) 的 第 \(k\) 小。

模板题：[ABC283G] Partial Xor Enumeration / https://www.luogu.com.cn/problem/AT_abc283_g

首先我们把基的每一个数都与别的数分离开来。

然后将不为 \(0\) 的数组成一个序列，直接查询异或和的第 \(k\) 小即可。

具体可以看代码。

/**
  * author : OMG_78
  * created: 2023-08-15-19.13.47
 **/
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/rope>
using namespace std;
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifdef LOCAL
#include "algo/debug.h"
#else
#define debug(...) 42
#endif
typedef long long ll;
typedef pair < int, int > PII;
typedef int itn;
mt19937 RND_MAKER (chrono :: steady_clock :: now ().time_since_epoch ().count ());
inline ll randomly (const ll l, const ll r) {return (RND_MAKER () ^ (1ull << 63)) % (r - l + 1) + l;}
//bool Mbes;
const double pi = acos (-1);
//__gnu_pbds :: tree < Key, Mapped, Cmp_Fn = std :: less < Key >, Tag = rb_tree_tag, Node_Upadte = null_tree_node_update, Allocator = std :: allocator < char > > ;
//__gnu_pbds :: tree < PPS, __gnu_pbds :: null_type, less < PPS >, __gnu_pbds :: rb_tree_tag, __gnu_pbds :: tree_order_statistics_node_update > tr;
inline bool statisqwq (char c) {
  if (c < '0') return true;
  if (c > '9') return true;
  return false;
}
inline int read () {
  int x = 0, f = 0;
  char c = getchar ();
  for ( ; statisqwq (c) ; c = getchar ()) f = (c == '-') ? 1 : f;
  for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
  return !f ? x : -x;
}
inline ll readll () {
  ll x = 0, f = 0;
  char c = getchar ();
  for ( ; statisqwq (c) ; c = getchar ()) f = (c == '-') ? 1 : f;
  for ( ; c >= '0' && c <= '9' ; c = getchar ()) x = (x << 1) + (x << 3) + (c & 15);
  return !f ? x : -x;
}
const ll hashmod1 = 2147483579;
const ll hashmod2 = 1610612741;
const ll hashmod3 = 805306457;
inline void chkmax (int &x, int y) {x = max (x, y);}
inline void chkmin (int &x, int y) {x = min (x, y);}
inline void chkmax2 (ll &x, ll y) {x = max (x, y);}
inline void chkmin2 (ll &x, ll y) {x = min (x, y);}
int n;
ll l, r;
struct linear_basis_awa {
  // If don't use "query_kth",
  // please "//" cy[64], bt[64], build_kth(), query_kth(k) and upd thanks meow!
  ll bs[64], cy[64], bt[64];
  int cnt, upd, num;
  inline void init () {
    upd = 1;
    for (int i = 0;i < 64; ++ i) bs[i] = 0;
    cnt = 0;
  }
  inline void ins (ll x) {
    if (!x) return ;
    upd = 1;
    for (int i = 62;i >= 0; -- i) {
      if (x & (1ll << i)) {
        if (bs[i]) x ^= bs[i];
        else {
          cnt ++;
          bs[i] = x;
          break;
        }
      }
    }
  }
  inline ll query_maxxor (ll x) {
    ll res = x;
    for (int i = 62;i >= 0; -- i) {
      if ((res ^ bs[i]) > res) res ^= bs[i];
    }
    return res;
  }
  inline void merge_bas (linear_basis_awa O) {
    for (int i = 0;i < 64; ++ i) ins (O.bs[i]);
  }
  inline void operator = (linear_basis_awa O) {
    for (int i = 0;i < 64; ++ i) bs[i] = O.bs[i];
    for (int i = 0;i < 64; ++ i) cy[i] = O.cy[i];
    upd = O.upd;
    cnt = O.cnt;
  }
  inline void build_kth () {
    upd = 0;
    for (int i = 0;i < 64; ++ i) cy[i] = bs[i], bt[i] = 0;
    for (int i = 62;i >= 0; -- i) {
      for (int j = i - 1;j >= 0; -- j) {
        if (cy[i] & (1ll << j)) cy[i] ^= cy[j];
      }
    }
    num = 0;
    for (int i = 0;i <= 62; ++ i) {
      if (cy[i]) bt[num ++] = cy[i];
    }
  }
  inline ll query_kth (ll k) {
    if (k == 1) return 0;
    k --;
    if (upd) build_kth ();
    if ((1ll << num) < k) return -1ll;
    ll ans = 0;
    for (int i = 0;i <= 62; ++ i) {
      if (k & (1ll << i)) {
        ans ^= bt[i];
      }
    }
    return ans;
  }
};
linear_basis_awa awa;
//bool Meds;
signed main () {
  n = read (), l = readll (), r = readll ();
  awa.init ();
  for (int i = 1;i <= n; ++ i) {
    ll w = readll ();
    awa.ins (w);
  }
  for (ll k = l;k <= r; ++ k) {
    printf ("%lld ", awa.query_kth (k));
  }
  printf ("\n");
  return 0;
}

~~好，这下线性基的操作你都会了，开始挑战黑题吧！~~

线性基，启动！