线性基

by JiuQiin 学习on Posted on

P3812 【模板】线性基 – 洛谷

Contents hide
1 题意
2 思路
3 代码
4 练习题目

题意

从一堆数中选取任意一些数，使的这些数异或和最大

思路

每当新插入一个数的时候，去判断在二进制下，它的最高位是否在线性基中出现过，如果出现过，则异或掉这一位（a[i] ^= d[i] ），依次往下进行判断，直到出现第一次在线性基中未发现该数的最高位，则将该数定为在改位下的线性基其中的一维，若最后异或的结果是零，则说明 a[i] 可由当前已有的线性基异或得到，他无法成为线性基中的一员。最后可获得当前数组对应的线性基

已知线性基中的每个数最高位的一的位置均不同，且从大到小排列，要求最大异或和，线性基的第一个一定会选，然后去看线性基中的下一个，若当前这个的位数在已有的答案中已经有一个 1 ，则若再异或，会消掉这个 1，使其变得更小，所以，跳过当前的基，反之，则异或，（异或后的结果对于比当前位小的位来说可能会变小，但是当前位一定是从零到一，一定会变大，那么整体一定是变大），依次往下按照同样的规则进行，直到得到最终答案，最后的答案一定是通过异或出来的线性基异或出来的结果，无论怎样，一定都是从原数组异或出来的结果

代码

#include <bits/stdc++.h>
using namespace std;
#define  endl '\n'
typedef long long LL;

void solve() {
    const LL LOG = 50;
    LL n;
    cin >> n;
    vector<LL> a(n + 1, 0), d(LOG + 1, 0);

    auto add = [&](LL x)
    {
        for (LL i = LOG; i >= 0; --i) { // 若要求最大异或和，则一定是从高到低位枚举
            if (!((x >> i) & 1)) continue; // 若当前位是零，则直接跳过
            if (!d[i]) { 
                d[i] = x;
                return; // 若当前位是一，并且在基中最高位的一并未有当前位，则加入进去
            }
            x ^= d[i]; // 若当前位是一，但在基中有相同的最高位的一，则先将当前位的一消掉，再进行下一位的判断
        }
    };

    // 创建线性基
    for (LL i = 1; i <= n; ++i) {
        cin >> a[i];
        add(a[i]);
    }
    
    // 构造最大异或和
    LL ans = 0;
    for (LL i = LOG; i >= 0; --i) {
        LL p = (ans >> i) & 1;
        if (d[i] && !p) {
            ans ^= d[i];
        }
    }
    cout << ans << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    
    LL T = 1;
    while (T--) {
        solve();
    } 
    return 0;
}

练习题目

F-永远亭的小游戏（续）_牛客周赛 Round 121

我觉得这是这道题最妙的地方：奇偶性->异或，完全平方数的特点是将其进行质因数分解，他的所有因子的指数都为偶数，同时 ai≤100a_i \leq 100 ，质数个数为 25，将 aia_i 其进行质因数分解，若其指数为奇数，则其因子对应的位置为一，反之为零，得出一个二进制数，其范围小于等于 2252^{25}，int 存的下

之后询问 [l, r][l, \ r] ，由于只要长度超过 25 就一定会有异或和等于零的存在，其等价于有若干数相乘的结果的因子的指数都为偶数，即该数为完全平方数，所以我们每次都可以把范围限定在 [l, min(r,l+25)][l, \ min(r, l + 25)] ，固定左端点，每次只需找向右扩展多长能得到异或和为零的结果或者无法异或为零

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const LL LOG = 26;

void solve() {
    int n, q;
    cin >> n >> q;
    vector<int> a(n + 1), b(n +1), d(30);

    vector<int> pos = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97};

    auto trans = [&](int x)
    {
        int y = 0;
        for (int i = 0; i < 25; ++i)
        {
            if (x % pos[i] == 0)
            {
                int cnt = 0;
                while (x > 0 && x % pos[i] == 0)
                {
                    ++cnt;
                    x /= pos[i];
                }
                if (cnt & 1)
                {
                    y |= (1 << i);
                }
            }
        }
        return y;
    };

    auto add = [&](int x)
    {
        for (int i = LOG; i >= 0; --i)
        {
            if (!(x >> i & 1))
                continue;
            if (!d[i])
            {
                d[i] = x;
                return true;
            }
            x ^= d[i];
        }
        return false;
    };

    for (int i = 1; i<= n; ++i) {
        cin >> a[i];
        b[i] = trans(a[i]);
    }

    for (int i = 1; i <= q; ++i) {
        int l, r;
        cin >> l >> r;
        r = min(r, l + 26);
        fill(d.begin(), d.end(), 0);
        int f = 0;
        for (int j = l; j <= r; ++j) {
            if (!add(b[j])) {
                f = 1;
                break;
            }
        }
        if (f) {
            cout << "Yes" << endl;
        }
        else {
            cout << "No" << endl;
        }
    }
}

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

    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}
xor序列

先建整个数组的线性基，然后去构造 x^y，是零的部分不管，是一的部分讨论一下

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const LL LOG = 31;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n + 1, 0), d(LOG  +1);

    auto add = [&](int x)
    {
        for (int i = LOG; i >= 0; --i) {
            if (!(x >> i & 1)) continue;
            if (!d[i]) {
                d[i] = x;
                return;
            }
            x ^= d[i];
        }
    };

    auto judge = [&](int x)
    {
        for (int i = LOG; i >= 0; --i) {
            if (!(x >> i & 1))
                continue;
            if (!d[i]) {
                return false;
            }
            x ^= d[i];
        }
        return true;
    };

    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
        add(a[i]);
    }
    
    int q;
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        cout << (judge(x ^ y) ? "YES" : "NO") << endl;
    }
}

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

    int T = 1;
    while (T--) {
        solve();
    }
    return 0;
}
P3857 [TJOI2008] 彩灯 – 洛谷 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const LL MOD = 2008;
const LL LOG = 50;

void solve()
{
    LL n, m;
    cin >> n >> m;

    vector<LL> a(m + 1, 0), d(LOG + 1, 0);
    for (LL i = 1; i <= m; ++i) {
        string s;
        cin >> s;
        for (LL j = 0; j < n; ++j) {
            if (s[j] == 'O') {
                a[i] |= (1LL << j);
            }
        }
    }

    auto add = [&](LL x)
    {
        for (LL i = LOG; i >= 0;--i) {
            if (!((x >> i) & 1)) continue;
            if (!d[i]) {
                d[i] = x;
                return;
            }
            x ^= d[i];
        }
    };

    for (LL i = 1; i <= m; ++i) {
        add(a[i]);
    }

    LL ans = 1;
    for (LL i = 0; i <= LOG; ++i) {
        if (d[i]) {
            ans = ans * 2 % MOD;
        }
    }

    cout << (ans == 1 ? 0 : ans) << endl;
}

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

    LL T = 1;
    while (T--) {
        solve();
    }
    return 0;
}
P4301 [CQOI2013] 新Nim游戏 – 洛谷

Nim游戏有个定则：异或和为零则先手必败，反之先手必胜。要想必胜，则必须满足：当我拿完的剩下的堆数中·，对手无论拿什么（除开全拿）都无法给我造成异或和为零的局面。 而，什么时候会造成异或和为零的局面？当剩下的堆数大于线性基的个数，并且剩下的是线性基以及再多任意一堆。那，如何避免当前局面，则剩下的都是线性基即可

现在问题转换成选出 kk 个线性基，并且 max(a1+a2+...+ak)max(a_1 + a_2 + … + a_k) ，如何使其最大？将 aa 数组从大到小依次加入到线性基中，第一次加入的一定是在原数组中所能找到的最大的值

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const LL LOG = 30;

void solve() {
    LL n;
    cin >> n;
    vector<LL> a(n+  1, 0), d(LOG + 1, 0);

    LL ans = 0;
    for (LL i = 1; i <= n; ++i) {
        cin >> a[i];
        ans += a[i];
    }

    sort(a.begin() + 1, a.end(), greater<LL>());


    auto add = [&](LL x)
    {
        LL y = x;
        for (LL i = LOG; i >= 0; --i)
        {
            if (!(x >> i & 1))
                continue;
            if (!d[i])
            {
                ans -= y;
                d[i] = x;
                return;
            }
            x ^= d[i];
        }
    };

    for (LL i = 1; i <= n; ++i) {
        add(a[i]);
    }

    cout << (ans == 0 ? -1 : ans) << endl;
}

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

    LL T = 1;
    while (T--) {
        solve();
    }
    return 0;
}
HDU 3949 XOR 
#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const LL LOG = 63;

void solve() {
    LL n;
    cin >> n;

    vector<LL> a(n+ 1, 0), d(LOG + 1, 0), p;

    auto add = [&](LL x)
    {
        for (LL i = LOG; i >= 0; --i) {
            if (!(x >> i & 1)) continue;
            if (!d[i]) {
                d[i] = x;
                return;
            }
            x ^= d[i];
        }
    };

    auto Gaussion = [&]() {
        for (LL i = LOG; i >= 0; --i) {
            if (!d[i]) continue;
            for (LL j = i - 1; j >= 0; --j) {
                if (d[i] >> j & 1) {
                    d[i] ^= d[j];
                }
            }
        }

        for (LL i = 0; i <= LOG; ++i) {
            if (!d[i]) continue;
            p.push_back(d[i]);
        }
    };

    for (LL i = 1; i <= n; ++i) {
        cin >> a[i];
        add(a[i]);
    }

    Gaussion();

    auto Kth = [&](long long k)
    {
        LL rank = p.size();

        if (rank < n)
        {
            k--;
        }

        if (k < 0)
        {
            return -1LL;
        }

        if (rank < 63 && k >= (1LL << rank))
        {
            return -1LL;
        }

        LL ans = 0;

        for (int i = 0; i < rank; i++)
        {
            if ((k >> i) & 1)
                ans ^= p[i];
        }

        return ans;
    };

    LL q;
    cin >> q;
    while (q--) {
        LL k;
        cin >> k;
        cout << Kth(k) << endl;
    }
}

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

    LL T = 1;
    while (T--) {
        solve();
    }
    return 0;
}
P4570 [BJWC2011] 元素 – 洛谷

这道题的思路类似于新Nim游戏，只是新Nim游戏是从原数组里面选取最大的 k 个，这个是根据魔力值选取最大的 k 个，本质一样，那道题前面的思考还要更绕一点

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const LL LOG = 60;

struct Node {
    LL id, w;
    Node () {}
    Node (LL id, LL w) : id(id), w(w) {}
    bool operator<(const Node &t) const {
        return w > t.w;
    }
};

void solve() {
    LL n;
    cin >> n;

    vector<Node> node(n + 1);
    vector<LL> d(LOG + 1, 0);

    for (LL i = 1; i <= n; ++i) {
        cin >> node[i].id >> node[i].w;
    }

    sort(node.begin() + 1, node.end());

    LL ans = 0;
    auto add = [&](LL x, LL w)
    {
        for (LL i = LOG; i >= 0; --i) {
            if (!(x >> i & 1)) continue;
            if (!d[i]) {
                d[i] = x;
                ans += w;
                return;
            }
            x ^= d[i];
        }
    };

    for (LL i = 1; i <= n; ++i) {
        auto [id, w] = node[i];
        add(id, w);
    }

    cout << ans << endl;
}

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

    LL T = 1;
    while (T--) {
        solve();
    }
    return 0;
}
P2447 [SDOI2010] 外星千足虫 – 洛谷

每次选取若干只千足虫，将他们的足数之和加起来模上2，这一过程等价于将他们的足数的奇偶性质异或起来，奇（1），偶（0），

1+1≡0 (mod 2), 1+0≡1(mod 2), 0+0≡0 (mod 2)1 + 1 \equiv 0\ (mod\ 2) ,\ 1 +0 \equiv 1(mod \ 2), \ 0 + 0\equiv 0\ (mod \ 2)，

1⊕︎1≡0 (mod 2), 1⊕︎0≡1 (mod 2), 0⊕︎0≡0 (mod 2)1\oplus 1 \equiv 0 \ (mod \ 2), \ 1 \oplus 0 \equiv 1 \ (mod\ 2), \ 0 \oplus 0 \equiv 0 \ (mod \ 2)

所以，每一次的统计相当于选取若干只千足虫的奇偶性异或起来，我们再联想到高斯消元最后获得的每个主元，相当于每次只选取一支千足虫，所获得的奇偶性质

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long LL;
const LL LOG = 1e3 + 10;

struct Node {
    string s;
    LL op;
    Node () {}
    Node (string s, LL op) : s(s), op(op) {}
};

void solve() {
    LL n, m;
    cin >> n >> m;

    vector<Node> node(m + 1);
    for (LL i = 1; i <= m; ++i) {
        cin >> node[i].s >> node[i].op;
    }

    vector<LL> d(n, 0);
    auto add = [&](LL id) -> LL
    {
        auto &[s, op] = node[id];
        for (LL i = 0; i < n; ++i)
        {
            if (!(s[i] - '0'))
                continue;
            if (!d[i])
            {
                d[i] = id;
                return 1LL;
            }
            auto [t, op1] = node[d[i]];
            op ^= op1;
            for (LL j = i; j < n; ++j)
            {
                LL a = s[j] - '0';
                LL b = t[j] - '0';
                LL c = a ^ b;
                s[j] = char(c + '0');
            }
        }
        return 0LL;
    };

    auto Gaussion = [&]()
    {
        for (LL i = 0; i < n; ++i) {
            auto &[s, op] = node[d[i]];
            for (LL j = i + 1; j < n; ++j) {
                if (!(s[j] - '0')) continue;
                auto [t, op1] = node[d[j]];
                op ^= op1;
                for (LL k = j; k < n; ++k) {
                    LL a = s[k] - '0';
                    LL b = t[k] - '0';
                    LL c = a ^ b;
                    s[k] = char(c + '0');
                }
            }
        }
    };

    LL ans = 0;
    for (LL i = 1; i <= m; ++i) {
        LL tmp = add(i);
        ans += tmp;
        if (ans == n) {
            cout << i << endl;
            Gaussion();
            for (auto v : d) {
                if (node[v].op == 1) {
                    cout << "?y7M#" << endl;
                }
                else {
                    cout << "Earth" << endl;
                }
            }
            return;
        }
    }

    cout << "Cannot Determine" << endl;
}

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

    LL T = 1;
    while (T--) {
        solve();
    }
    return 0;
}
Problem – 241B – Codeforces

albus就是要第一个出场

Problem – 959F – Codeforces

SPOJ.com – Problem XMAX

P4151 [WC2011] 最大 XOR 和路径 – 洛谷

[JLOI2015]装备购买

[SCOI2016]幸运数字

CF1100F Ivan and Burgers – 洛谷

CF1902F Trees and XOR Queries Again – 洛谷

「猫是可爱的，狼是很帅的。就是说，孤独又可爱又帅。」
— 我的青春恋爱物语果然有问题
Post authorWritten by

Leave a Comment

您的邮箱地址不会被公开。 必填项已用 * 标注