线性基基础知识

【算法学习笔记】03 线性基

定义

对于一个数列 A 来说，P 是他的线性基当且仅当

A任意数字都能通过P中的一些数字异或出来
P只能异或出A中的数或A中的数能异或出来的东西
P中任意数都不能被P中其他数异或出来
P中数最高位不重复

故，A中数可以异或出来的最大值就是P中数可以异或出来的最大值

线性基是一个上三角矩阵的形式，其对角线全为1

怎么求

原理：每次都把现在没有的最高位1插入，因为如果不选1那么以后再也没有一个数可以使得最高位为1了

每插入一个数的时候都比较最高位：

如果要插入的数最高位没有（当前线性基中没有数能表示它），那么直接插入，break
如果要插入的数最高位已有（就表示该数可以由线性基中有的数表示出来），则异或上这个已有的数（消去最高位），直至最高位不在线性基中，才可插入或者最终变为0（不插入）

演示一下该过程：
现有5个数，从大到小放入线性基
首先1001满足最高位没有，直接插入；同理0111也是直接插入；

到了0110的时候，最高位已有0111，故先与之异或，得0001，故放入相应得位置

下一个是0011，最高位没有，直接插入

最后一个数0010经处理过后得0

template:
插入（构造线性基）

bool insert (ll x) {
    for (int i = 62; i >= 0; i--) {
        if ((x >> i & 1) == 0)  continue;
        if (num[i] == 0) {
            num[i] = x;
            return true;
        }
        else    x ^= num[i];
    }
    return false;
}

模板题：https://www.luogu.com.cn/problem/P3812
打卡记录：https://www.acwing.com/activity/content/code/content/4056208/

性质

1. 求生成空间里总共有多少个不同的数字

2^cnt^ 个，cnt 为线性基中数的个数
可由线性基的构造得此结论

2. 求该数能否被线性基表示

从高位依次往下消，如果最后被消成0，则能被表示

查询x是否能被线性基表示 / 求x与线性基子集的最小异或和

ll querymin (ll x) {
    for (int i = 62; i >= 0; i --) {
        x = min (x, x ^ num[i]);
    }
    return x;
}

求x与线性基子集的最大异或和

ll querymax (ll x) {
    for (int i = 62; i >= 0; i --) {
        x = max (x, x ^ num[i]);
    }
    return x;
}

板子纯享版

struct linear_basis {
    ll num[63];
    bool insert (ll x) {
        for (int i = 62; i >= 0; i--) {
            if ((x >> i & 1) == 0)  continue;
            if (num[i] == 0) {
                num[i] = x;
                return true;
            }
            else    x ^= num[i];
        }
        return false;
    }

    ll querymin (ll x) {
        for (int i = 62; i >= 0; i --) {
            x = min (x, x ^ num[i]);
        }
        return x;
    }

    ll querymax (ll x) {
        for (int i = 62; i >= 0; i --) {
            x = max (x, x ^ num[i]);
        }
        return x;
    }
}T;

例题

线性基第k大

题目

样例输入：

1 2	4 5 1 4 5 8

样例输出：

分析

#include <bits/stdc++.h>
#define int long long

using namespace std;
const int N = 1e5 + 5;
int  num[N], n, k, q, zero;

bool insert (int x) {
    for (int i = 62; i >= 0; i--) {
        if ((x >> i & 1) == 0)  continue;
        if (num[i] == 0) {
            num[i] = x;
            return true;
        }
        else    x ^= num[i];
    }
    return false;
}

signed main () {
    cin >> n;
    for (int i = 0; i < n; i ++) {
        int x;
        cin >> x;
        if (!insert (x))    zero ++;
    }
    cin >> q;
    while (q --) {
        cin >> k;
        k >>= zero;
        vector <int> v;
        for (int i = 0; i <= 62; i++)
            if (num[i]) v.push_back (num[i]);
        int m = v.size();

        int ans = 0;
        for (int i = m-1; i >= 0; i--) {
            if (k >> i & 1)     ans = max (ans, ans^v[i]);
            else    ans = min (ans, ans^v[i]);
        }

        cout << ans << endl;
    }
}

[WC2011]最大XOR和路径

https://www.luogu.com.cn/problem/P4151

任找一棵生成树
走了一条非树边就相当于多异或了一个环

即 找出所有环，放入线性基，随便找一条链，以它作为初值求最大异或和

转化为子问题：
求出所有的环 + 一个数异或若干个数的最大值

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
typedef pair<int, ll> pii;

const int N = 5e4 + 5;
ll dis[N];
int n, m;
bool vis[N];
vector <pii> e[N];

struct linear_basis {
    ll num[63];
    bool insert (ll x) {
        for (int i = 62; i >= 0; i--) {
            if ((x >> i & 1ll) == 0)  continue;
            if (num[i] == 0) {
                num[i] = x;
                return true;
            }
            else    x ^= num[i];
        }
        return false;
    }

    ll querymin (ll x) {
        for (int i = 62; i >= 0; i --) {
            x = min (x, x ^ num[i]);
        }
        return x;
    }

    ll querymax (ll x) {
        for (int i = 62; i >= 0; i --) {
            x = max (x, x ^ num[i]);
        }
        return x;
    }
}T;

void dfs (int u) { //枚举所有环
    vis[u] = true;
    for (auto vi : e[u]) {
        int v = vi.first;
        ll w = vi.second;
        if (!vis[v]) {
            dis[v] = dis[u] ^ w;
            dfs (v);
        }
        else {
            T.insert (dis[u] ^ dis[v] ^ w); //环的异或和
        }
    }
}

int main () {
    cin >> n >> m;
    for (int i = 0; i < m; i ++) {
        int u, v; ll w;
        cin >> u >> v >> w;
        e[u].push_back ({v, w});
        e[v].push_back ({u, w});
    }
    dfs (1);
    cout << T.querymax(dis[n]) << endl;
}

F - Spices

再来一到比较裸的，atc的
https://atcoder.jp/contests/abc236/tasks/abc236_f

题意：在集合S中选择一些数字进行异或和
可以得到 1∼2^n−1^ 之间的所有数字，求最小的花费。

分析：线性基模板，排个序，套板子即可

#include <bits/stdc++.h>
#define int long long

using namespace std;
typedef pair<int, int> pii;
const int N = 20;
int c[N], n, m;

signed main () {
    cin >> n;
    m = 1 << n;
    vector <pii> v;
    for (int i = 1; i < m; i ++) {
        int x;
        cin >> x;
        v.push_back ({x, i});
    }
    sort (v.begin(), v.end()); //按照花费从小到大排

    int ans = 0;
    vector <int> t(n+1, 0); //线性基
    for (auto vi : v) {
        int val = vi.first, x = vi.second;
        for (int i = 0; i < n; i ++) {
            if ((x >> i & 1) == 0)  continue;
            if (t[i] == 0) { //更新线性基
                ans += val;
                t[i] = x;
                break;
            }
            else    x ^= t[i];
        }
    }

    cout << ans << endl;
}


//在集合S中选择一些数字进行异或和
//可以得到1∼2^n−1之间的所有数字，求最小的花费。

//线性基模板

Reference:

未完待续