可用下标访问主元在第 \(i\) 位的基.

insert方法返回插入值是否与当前线性基线性相关. +上注释掉的几行则得到的线性基正交.

\(1 \sim 64\) 位.

using uLL = unsigned long long;
template <const int n = 64>
struct LinearBasis {
    std::array<uLL, n> ans;
    LinearBasis() : ans() {}
    bool insert(uLL x) {
        for (int i = n - 1; i >= 0 && x; i--) {
            if (!(x >> i & 1))
                continue;
            if (ans[i]) {
                x ^= ans[i];
            } else {
                // for (int j = i - 1; j >= 0; j--) {
                //     if (x >> j & 1 && ans[j]) {
                //         x ^= ans[j];
                //     }
                // }
                // for (int j = n - 1; j > i; j--) {
                //     if (ans[j] >> i & 1) {
                //         ans[j] ^= x;
                //     }
                // }
                ans[i] = x;
                return 1;
            }
        }
        return 0;
    }
    auto &&operator[](int x) const { return ans[x]; }
};

64位+. 下标访问直接返回一个bitset.

template <const int n = 64>
struct LinearBasis {
    std::array<std::bitset<n>, n> ans;
    LinearBasis() : ans() {}
    bool insert(std::bitset<n> x) {
        for (int i = n - 1; i >= 0 && x.any(); i--) {
            if (!x[i])
                continue;
            if (ans[i].any()) {
                x ^= ans[i];
            } else {
                // for (int j = i - 1; j >= 0; j--) {
                //     if (x[j] && ans[j].any()) {
                //         x ^= ans[j];
                //     }
                // }
                // for (int j = n - 1; j > i; j--) {
                //     if (ans[j][i]) {
                //         ans[j] ^= x;
                //     }
                // }
                ans[i] = x;
                return 1;
            }
        }
        return 0;
    }
    auto &&operator[](int x) const { return ans[x]; }
};