登录
← 返回首页 | 代码片段 › 7 数论与数学 › 7.6 线性基 › 线性基 / 搜索
JSON MD

7.6 线性基

异或线性基 xianxingji
17 行
CPP JSON
【异或线性基(XOR Basis)】 ▪ Basis() — 构造函数,memset 清零 60 位基数组 a[] ▪ ins(x) — 插入数 x 到线性基:从高位向低位扫描,若 x 第 i 位为 1:若 a[i]==0 则 a[i]=x 返回 true(成功插入);否则 x^=a[i] 继续消去该位。返回 false 表示 x 可被已有基线性表出 ▪ max_val(x=0) — 查询与 x 异或的最大值:贪心从高到低,若 (x^a[i])>x 则 x^=a[i] 基的大小 ≤60(long long 位数)。适用于最大异或和、判断数是否可被表出、线性基求第 k 小异或和等。
C++ 17 行 CPP
struct Basis{
    static const int K=60;
    ll a[K];
    Basis(){memset(a,0,sizeof a);}
    bool ins(ll x){
        for(int i=K-1;~i;--i)
        if(x>>i&1){
            if(!a[i]){a[i]=x;return true;}
            x^=a[i];
        }
        return false;
    }
    ll max_val(ll x=0){
        for(int i=K-1;~i;--i)if((x^a[i])>x)x^=a[i];
        return x;
    }
}B;
前缀基 b
38 行
CPP JSON
【前缀基(b)】 前缀线性基模板,维护每个位置的前缀线性基并可查询区间异或最大值。 核心函数: ll qpow(ll a, ll b) — 快速幂 void linear_inv(const std::vector<ll>& a, std::vector<ll>& inv_a) — 求模逆元 关键配置: MOD=998244353
C++ 38 行 CPP
#include <iostream>
#include <vector>

using ll = long long;
using namespace std;
const int MOD = 998244353;

ll qpow(ll a, ll b) {
    ll res = 1;
    a %= MOD;
    while (b) {
        if (b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

/**
 * 线性批量求逆元 (前缀积法)
 * 传入需要求逆元的数组 a (1-indexed),将结果存入 inv_a (1-indexed)
 * 时间复杂度: O(n + log(MOD))
 */
void linear_inv(const std::vector<ll>& a, std::vector<ll>& inv_a) {
    int n = a.size() - 1;
    if (n <= 0) return;
    std::vector<ll> pre(n + 1, 1), inv_pre(n + 1, 1);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] * a[i] % MOD;
    }
    inv_pre[n] = qpow(pre[n], MOD - 2);
    for (int i = n; i >= 1; i--) {
        inv_pre[i - 1] = inv_pre[i] * a[i] % MOD;
    }
    for (int i = 1; i <= n; i++) {
        inv_a[i] = inv_pre[i] * pre[i - 1] % MOD;
    }
}
已复制