关于算法:OierBBS文章推荐-2-笔记线性基

36次阅读

共计 9641 个字符，预计需要花费 25 分钟才能阅读完成。

原文链接：https://oierbbs.fun/blog/399/3

作者：@”Suzt_ilymtics”#38

举荐工夫：2021 年 8 月 13 日

更好的浏览体验？

概念

线性基是向量空间的一组基，通常能够解决无关异或的一些题目。-Oi-wiki

线性基就是一个有着非凡性质的汇合，在解决某些状况下的异或问题有着意想不到的成果。

假如咱们用 p 数组来存线性基。

线性基能够由给出的一组元素互相异或而来。

而 p_i 中的元素示意该元素二进制下 1 的最高位是第 i 位。

性质

  • 线性基具备一般汇合所具备的性质，即确定性、互同性、无序性。
  • 线性基中每个元素的最高位不同。（依据 p 数组定义比拟显然。）
  • 线性基中没有异或和为 0 的子集。（每个元素的最高位不同，异或起来最高位肯定不会为 0。）
  • 线性基中任意多元素的异或和的值域等于原汇合中任意多元素的异或和的值域。
  • 线性基在满足上一个条件的状况下，所蕴含元素个数是起码的。
  • 线性基中不同的元素异或进去的值是不同的。

结构

个别状况下都是在二进制下进行。

假如插入一个元素为 x。

  • 从高位向低位判断，直到遇到该元素某位上为 1，设该位为 i。
  • 而后判断 p_i 是否有值，如果没有把 x 存到 p_i 中，否则将 x 与 p_i 异或而后反复下面的操作。（将 x 与 p_i 异或后 x 的最高位上的 1 就没了，至于变成了啥也无所谓了）

把所有元素都插入后，咱们就失去了这组元素的线性基。

这样结构的线性基满足它该有的所有性质，p_i 数组也合乎定义。

Code：

void Insert(int k) {for(int i = Max; i >= 0; --i) { // Max 示意二进制最高位
        if(!(k & (1ll << i))) continue;
        if(!p[i]) {p[i] = k; return ; }
        k ^= p[i];
    }
}

线性基的插入和上面的几个操作复杂度都是 O(\log n) 的。

操作

求最大值

给你一堆元素，挑几个异或起来，是他们的值最大，输入最大值。

咱们先用这组元素结构出线性基。而后贪婪的进行抉择，选高位的必定比低位的要更优。

所以咱们从高位向低位遍历，如果异或上 p_i 更优就异或。最初的后果就是要求的最大值。

为什么能间接用？线性基的元素都是通过已知的元素异或而来，必定是正确的。

Code:

int Query() {
    int res = 0; 
    for(int i = Max; i >= 0; --i) res = max(res, res^p[i]);
    return res;

求一个数是否能被示意进去

把这个数扔到线性基里跑一边就行。

每次挑这个数的最高位进行异或，都能把最高位消掉。

如果最初这个数为 0，阐明该数能够被示意出。

线性基合并

把一个线性基的每个元素插入另外一个线性基即可。

查找严格次大值

先找到最大值，而后从低位向高位枚举，而后找到两者都为一的异或上, 而后退出即可。

狭义线性基

之前咱们只是把线性基简单化了，线性基最后是利用到向量里的。

例题

这道题思路和 [P4570 [BJWC2011] 元素](https://www.luogu.com.cn/prob… 挺像的。

只不过这道题把整数换成了向量。向量中的每个元素就相当于原来的每个二进制位。

咱们能够把 n 个配备看作 n 个 m 维的向量。

如 k = (a_1, a_2, a_3, ... , a_m)

大体思路是一样的，联合高斯消元来结构。

emm 看代码会更直观一点，感觉我口胡的并不是很分明。

/*
Work by: Suzt_ilymics
Knowledge: ??
Time: O(??)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#include<string>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
const double lim = 1e-5; // lim 避免因精度损失而引发谬误

int n, m, cnt = 0;
int sum = 0;

struct Vector { // 这里把所有向量存到了构造体里方便使用
    int cost;
    double a[520]; // a 数组存向量的每个元素的值
    Vector () { for(int i = 1; i <= m; ++i) a[i] = 0; }
    bool operator < (const Vector &b) const {return cost < b.cost;}
    Vector operator + (const Vector b) { 
        Vector res;
        for(int i = 1; i <= m; ++i) res.a[i] = a[i] + b.a[i];
        return res;
    }
    Vector operator - (const Vector b) {
        Vector res;
        for(int i = 1; i <= m; ++i) res.a[i] = a[i] - b.a[i];
        return res;
    }
    Vector operator * (const double b) { 
        Vector res;
        for(int i = 1; i <= m; ++i) res.a[i] = a[i] * b;
        return res;
    }
}ep[520]; // 存读入的每个向量

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

namespace Lb {Vector p[520];
    bool Insert(Vector k) {for(int i = m; i >= 1; --i) { // 从左向右顺次遍历每个向量中的元素，这里的遍历程序已不再重要
            if(abs(k.a[i]) < lim) continue; // 如果插入向量的以后元素无值就跳过
            if(abs(p[i].a[i]) < lim) {p[i] = k; return true; } // 如果线性基中“最高位”向量中没有值，就插入。double t = k.a[i] / p[i].a[i]; // 算出系数
            k = k - p[i] * t; // 进行消元
        }
        return false;
    }
}

int main()
{n = read(), m = read();
    for(int i = 1; i <= n; ++i) 
        for(int j = 1; j <= m; ++j) 
            scanf("%lf", &ep[i].a[j]); // 读入 n 个 向量
    for(int i = 1; i <= n; ++i) ep[i].cost = read(); // 读入每个向量的破费，类比元素那道题
    sort(ep + 1, ep + n + 1); // 依照破费从小到大排序贪婪
    for(int i = 1; i <= n; ++i) {if(Lb::Insert(ep[i])) { // 判断是否插入
            ++ cnt; // 计数
            sum += ep[i].cost; // 记录破费
        }
    }
    printf("%d %d", cnt, sum);
    return 0;
}

例题

P3812【模板】线性基

题目传送

板子题，求最大值。

/*
Work by: Suzt_ilymics
Problem: 不出名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
const int bit = 50;

int n, p[55];

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

void Insert(int k) {for(int i = bit; i >= 0; --i) {if(!(k & (1ll << i))) continue;
        if(!p[i]) {p[i] = k; return ; }
        k ^= p[i];
    }
}

int Maxxor() {
    int res = 0;
    for(int i = bit; i >= 0; --i) res = max(res, (res ^ p[i]));
    return res;
}

signed main()
{n = read();
    while(n--) Insert(read());
    printf("%lld", Maxxor());
    return 0;
}

P3857 [TJOI2008]彩灯

题目传送

搞出线性基，统计线性基中有几个元素，假如有 x 个，输入 2^ x \bmod 2008 即可。

因为假如咱们有 p_i 那么选与不选肯定会决定第 i 位的是否为 1，那么有几个 p_i 咱们就能决定几位，答案也就是 2^ x。

/*
Work by: Suzt_ilymics
Problem: 不出名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 2008;
const int Max = 50;

char s[60];
int n, m, cnt = 0;
int p[60];

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

void Insert(int k) {for(int i = Max; i >= 0; --i) {if(!(k & (1ll << i))) continue;
        if(!p[i]) {p[i] = k; return ;}
        k ^= p[i];
    }
}

signed main()
{n = read(), m = read();
    for(int i = 1; i <= m; ++i) {scanf("%s", s + 1);  int x = 0;
        for(int j = 1; j <= n; ++j) if(s[j] == 'O') x |= (1ll << (j - 1));
        Insert(x);
    }
    for(int i = Max; i >= 0; --i) if(p[i]) cnt++;
    printf("%lld\n", (1ll << cnt) % mod);
    return 0;
}

P4570 [BJWC2011]元素

题目传送

首先咱们晓得

如果 a \oplus b = c，那么 a \oplus c = b, b \oplus c = a。

由后面推前面能够看做两边同时异或 a 或者 b。

假如 b_1 \oplus b_2 \oplus b_3 ... \oplus b_i = x ，x 比任何一个值都要大。

那么 x \oplus b_ 1 \oplus b_ 2 \oplus b_ 3 ... \oplus b_ {i-1} = b_ i。

为了取得更大价值，咱们能够依照价值从大到小排序，而后贪婪的抉择。

每次向线性基插入它的 number，如果能够插入就抉择它。

/*
Work by: Suzt_ilymics
Problem: 不出名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

struct node {
    LL k, val;
    bool operator < (const node &b) const {return val > b.val;}
}a[MAXN];

LL n, ans = 0;

LL read(){
    LL s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

namespace Lb {
    const LL Max = 60;
    LL p[61];
    bool Insert(LL k) {for(LL i = Max; i >= 0; --i) {if(!(k & (1ll << i))) continue;
            if(!p[i]) {p[i] = k; return true; }
            k ^= p[i];
        }
        return false;
    }
}

int main()
{n = read();
    for(int i = 1; i <= n; ++i) a[i].k = read(), a[i].val = read();
    sort(a + 1, a + n + 1);
    for(int i = 1; i <= n; ++i) if(Lb::Insert(a[i].k)) ans += a[i].val;
    printf("%lld", ans);
    return 0;
}

P4151 [WC2011]最大 XOR 和门路

题目传送

乍一看没有思路。一开始认为能够像下面那个题一样贪婪的抉择。

因为能够反复通过，所以门路就太多了。

假如咱们走到了 n 号点，咱们此时的异或和为 dis_n。

咱们想要晓得有没有更优的抉择，咱们假如往回走某条咱们没有通过的门路，如果咱们不能绕回来，也就是说没有环，那么在返回的途中还会再走一遍。家喻户晓 x \oplus x = 0。所以就相当于咱们啥也没干。

如果在走的途中绕了一个环，咱们从环的终点登程又回到了环的终点，环上的门路都只被走了一次，阐明什么？咱们与环上的所有值异或了。

通过下面探讨不难发现，个别门路上的值不能选，环上的值可选可不选，那么咱们把一个环当做一个元素构建线性基，挑几个能让咱们的 dis_n 变得更优的与之异或。

dis_n 怎么求？轻易找一条门路。

如果有更优的门路，那么它肯定会与这条门路造成一个环，异或这个环，就会变成抉择另一条门路。

/*
Work by: Suzt_ilymics
Problem: 不出名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define LL long long
#define int long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 1e5+5;
const int INF = 1e9+7;
const int mod = 1e9+7;
const int Max = 61;

struct edge {int to, w, nxt;}e[MAXN << 1];
int head[MAXN], num_edge = 1;

int n, m;
int p[66], dis[MAXN];
bool vis[MAXN];

int read(){
    int s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

void add_edge(int from, int to, int w) {e[++num_edge] = (edge){to, w, head[from]}, head[from] = num_edge; }

void Insert(int k) {for(int i = Max; i >= 0; --i) {if(!(k & (1ll << i))) continue;
        if(!p[i]) {p[i] = k; return ; }
        k ^= p[i];
    }
}

int Query(int res) {for(int i = Max; i >= 0; --i) res = max(res, res ^ p[i]);
    return res;
}

void dfs(int u, int sum) {dis[u] = sum, vis[u] = true;
    for(int i = head[u]; i; i = e[i].nxt) {int v = e[i].to;
        if(!vis[v]) dfs(v, dis[u] ^ e[i].w);
        else Insert(dis[u] ^ dis[v] ^ e[i].w);
    }
}

signed main()
{n = read(), m = read();
    for(int i = 1, u, v, w; i <= m; ++i) {u = read(), v = read(), w = read();
        add_edge(u, v, w), add_edge(v, u, w);
    }
    dfs(1, 0);
    printf("%lld\n", Query(dis[n]));
    return 0;
}

P3292 [SCOI2016]侥幸数字

题目传送

把每个点看做一个线性基而后树剖即可。

询问时把每段区间的线性基合并求最大值即可。

总复杂度 O(n \log ^ 4n)。

代码写的比拟丑，须要吸氧能力过。

/*
Work by: Suzt_ilymics
Problem: 不出名屑题
Knowledge: 垃圾算法
Time: O(能过)
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<queue>
#define LL long long
#define orz cout<<"lkp AK IOI!"<<endl

using namespace std;
const int MAXN = 2e4+5;
const int INF = 1e9+7;
const int mod = 1e9+7;

struct edge {int to, nxt;}e[MAXN << 1];
int head[MAXN], num_edge = 1;

int n, Q, cnt = 0;
LL a[MAXN];
int dep[MAXN], fath[MAXN], siz[MAXN], son[MAXN], top[MAXN], dfn[MAXN], pre[MAXN];

LL read(){
    LL s = 0, f = 0;
    char ch = getchar();
    while(!isdigit(ch))  f |= (ch == '-'), ch = getchar();
    while(isdigit(ch)) s = (s << 1) + (s << 3) + ch - '0' , ch = getchar();
    return f ? -s : s;
}

void add_edge(int from, int to) {e[++num_edge] = (edge){to, head[from]}, head[from] = num_edge; }

namespace Seg {
    #define lson i << 1
    #define rson i << 1 | 1
    struct Tree {LL p[66];
        Tree () { memset(p, false, sizeof p); }
        void Insert(LL k) {for(int i = 60; i >= 0; --i) {if(!(k & (1ll << i))) continue;
                if(!p[i]) {p[i] = k; return ; }
                k ^= p[i];
            }
        }
        LL Query() {
            LL res = 0;
            for(int i = 60; i >= 0; --i) res = max(res, res ^ p[i]);
            return res;
        } 
    }tree[MAXN << 2];
    void Push_up(int i) {tree[i] = tree[lson];
        for(int j = 60; j >= 0; --j) if(tree[rson].p[j]) tree[i].Insert(tree[rson].p[j]);
    }
    void hb(Tree *x, Tree y) {for(int i = 60; i >= 0; --i) if(y.p[i]) x->Insert(y.p[i]); }
    void Build(int i, int l, int r) {if(l == r) {tree[i].Insert(a


]);

            return ;

        }

        int mid = (l + r) >> 1;

        Build(lson, l, mid), Build(rson, mid + 1, r);

        Push_up(i);

    }

    Tree Query(int i, int l, int r, int L, int R) {

        if(L <= l && r <= R) return tree[i];

        Tree ans;

        int mid = (l + r) >> 1;

        if(mid >= L) ans = Query(lson, l, mid, L, R);

        if(mid < R) hb(&ans, Query(rson, mid + 1, r, L, R));

        return ans;

    }

}


namespace Cut {

    void dfs(int u, int fa) {

        dep[u] = dep[fa] + 1, fath[u] = fa, siz[u] = 1;

        for(int i = head[u]; i; i = e[i].nxt) {

            int v = e[i].to;

            if(v == fa) continue;

            dfs(v, u);

            siz[u] += siz[v];

            if(siz[son[u]] < siz[v]) son[u] = v;

        }

    }

    void dfs2(int u, int tp) {

        top[u] = tp, dfn[u] = ++ cnt, pre[cnt] = u;

        if(son[u]) dfs2(son[u], tp);

        for(int i = head[u]; i; i = e[i].nxt) {

            int v = e[i].to;

            if(v == fath[u] || v == son[u]) continue;

            dfs2(v, v);

        }

    }

    Seg::Tree Query(int x, int y) {

        Seg::Tree ans;

        while(top[x] != top[y]) {

            if(dep[top[x]] < dep[top[y]]) swap(x, y);

            Seg::hb(&ans, Seg::Query(1, 1, n, dfn[top[x]], dfn[x]));

            x = fath[top[x]];

        }

        if(dep[x] > dep[y]) swap(x, y);

        Seg::hb(&ans, Seg::Query(1, 1, n, dfn[x], dfn[y]));

        return ans;

    }

}


signed main()

{

    n = read(), Q = read();

    for(int i = 1; i <= n; ++i) a[i] = read();

    for(int i = 1, u, v; i < n; ++i) u = read(), v = read(), add_edge(u, v), add_edge(v, u);

    Cut::dfs(1, 0), Cut::dfs2(1, 1), Seg::Build(1, 1, n);

    for(int i = 1, u, v; i <= Q; ++i) {

        u = read(), v = read();

        Seg::Tree ans = Cut::Query(u, v);

        printf("%lld\n", ans.Query());

    }

    return 0;

}


鸣谢


题解 P3812【模板】线性基 – rui_er


线性基常识整顿 – Aliemo


线性基 – KnightL




 
 
 
正文完
 
 
 算法
 
 
 发表至： 算法 
 
  2021-08-13 
 
 
 
 
 
 
 
  0
 
 
 
 
 
 
 
 
 
  
 
   
 
关于供应链:三只松鼠阿里云数据中台基座上的多渠道多业态生长
 
    
 
关于算法:笔试算法题总结
 
    
 
关于算法:常见排序算法实现TS-版
 
    
 
关于算法:SLAM技术支持的物体6Dof位姿估计的自训练方法