xor基底

[Astral-23]

コードは書いた atcoderで試した atcoderはauto_verifyで(この環境では)使えない

struct bitbase {
    int K = 60;
    int sz;
    vec<ll> d;

    bitbase() : d(K, 0), sz(0) {}

    ll tomin(ll x) {
        rrep(i, 0, K) if(x >> i & 1) x ^= d[i];
        return x;
    }

    void add(ll x) {
        x = tomin(x);
        rrep(i, 0, K) if(x >> i & 1) {
            rep(j, 0, K) {
                if(d[j] >> i & 1) d[j] ^= x;
            }
            d[i] = x;
            sz++;
            return;
        }
    }

    int rank() {
        return sz;
    }

    bool can(ll x) {
        rrep(i, 0, K) if(x >> i & 1) x ^= d[i];
        return x == 0;
    }

    ll kth(ll k) {
        vec<int> able;
        rep(i, 0, K) if(d[i]) able.push_back(i);

        ll res = 0;

        rep(i, 0, able.size()) if(k >> i & 1) {
            k ^= (1LL << i);
            res ^= d[able[i]];
        }

        if(k) return -1;//存在しない
        return res;
    }
};

https://atcoder.jp/contests/code-thanks-festival-2017-open/submissions/54047105

[Astral-23]

サイズでかい版 N <= 3000ぐらい？ 1回の追加に(k ^ 2 / 64)

template <int k> struct bitbase {
    using BS = bitset<k>;
    int sz;
    vec<BS> d;

    bitbase() : sz(0), d(k, 0) {}
    BS tomin(BS &x) {
        rrep(i, 0, k) if (x[i]) x ^= d[i];
        return x;
    }

    void add(BS x) {
        tomin(x);
        rrep(i, 0, k) if (x[i]) {
            rep(j, 0, k) {
                if (d[j][i]) d[j] ^= x;
            }
            d[i] = x;
            sz++;
            return;
        }
    }

    int rank() { return sz; }

    bool can(BS x) {
        rrep(i, 0, k) if (x[i]) x ^= d[i];
        return x == 0;
    }
};

const int K = 5000;
using BS = bitset<K>;