实数下的线性基

例题 洛谷P3265 (opens new window)

注意精度问题，要么用long double(GCC有效，VC无效，其他编译器不清楚)，要么将eps调大并祈求数据不要太刁钻

见代码

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

using namespace std;

const int maxm = 500 + 10;

struct vec{
    long double val[maxm];
};

const long double eps = 1e-7;
struct linear_base{
    vec base[maxm];
    bool has_val[maxm];
    int m;
    bool is_zero(long double v){return fabs(v) < eps;}

    void init(int bits){
        m = bits;
        for(int i=0; i<=bits; i++) has_val[i] = false;
    }

    bool insert(vec vect){
        for(int i=0; i<m; i++){
            if(!is_zero(vect.val[i])){
                if(!has_val[i]){
                    has_val[i] = true;
                    base[i] = vect;
                    return true;
                }
                long double k = vect.val[i] / base[i].val[i];
                for(int j=i; j<m; j++) vect.val[j] -= k * base[i].val[j];
            }
        }
        return false;
    }
}lb;

struct item{
    vec vect;
    ll cost;
    bool operator <(const item & other)const{
        return cost < other.cost;
    }
}items[maxm];

void solve(){
    int n, m;
    cin >> n >> m;
    lb.init(m);
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++) cin >> items[i].vect.val[j];
    }
    for(int i=0; i<n; i++) cin >> items[i].cost;
    sort(items, items + n);
    
    ll cost = 0, cnt = 0;
    for(int i=0; i<n; i++){
        if(lb.insert(items[i].vect)){
            cost += items[i].cost, cnt++;
        }
    }
    cout << cnt << " " << cost << endl;
}

int main(){
    solve();
}

二进制异或下的线性基

例题 Codeforces 587E (opens new window) 差分线性基

题意：给定$a_1,a_2,...a_n$，进行下列两种操作

1. 对$a_i\ i\in[l, r] \oplus x$
2. 求$a_i\ i\in[l, r]$通过异或操作能够表示出的数的数量

对于操作2，显然是求$a_l...a_r$中"异或不相关"(参考线性不相关的概念)的个数$x$，答案为$2^x$，可用线性基求解

根据题解 (opens new window)，$a_l, a_{l+1}, ..., a_r$所能表出的数，都能由$a_l, a_l\oplus a_{l+1}, a_{l+1}\oplus a_{l+2}, ..., a_{r-1}\oplus a_r$表出。

令$b_i=a_{i-1}\oplus a_i$，考虑操作1$([l, r], x)$

该操作只会对$b_l,b_{r+1}$造成影响，只需将$b_l$修改为$b_l \oplus x$（$b_{r+1}$同理）即可！

因此我们用一棵线段树来维护$b_2...b_n$，再用一个别的什么（线段树/树状数组之类的）来维护$a_i$就好

#include <bits/stdc++.h>
#define Android ios::sync_with_stdio(false), cin.tie(NULL)
#define mid(a, b) ((a + b) >> 1)

using namespace std;

const int maxn = 2e5 + 1000;

struct basis{
    int b[33];
    basis(){memset(b, 0, sizeof b);}
    void add(int val){
        for(int i=31; i>=0 && val != 0; i--){ 
            if(val & (1<<i)){// 这里注意'>'/'!='/'=='操作符的优先级高于'&'
                if(b[i] == 0) b[i] = val;
                val ^= b[i];
            }
        }
    }

    void set(int val){
        int k = 0;
        for(int i=31; i>=0 && k == 0; i--) k = b[i];
        memset(b, 0, sizeof b);
        add(val ^ k);
    }

    basis operator ^(const basis & other){
        basis ret = other; 
        for(int i=31; i>=0; i--) if(b[i]) ret.add(b[i]);
        return ret;
    }

    int count(){
        int cnt = 0;
        for(int i=0; i<32; i++) cnt += (b[i] != 0);
        return cnt;
    }
};

struct segment_tree_b{
    basis tree[4 * maxn];

    void build(int * data, int l, int r, int rt){
        if(l == r){
            tree[rt].add(data[l]);
            return;
        }
        int mid = mid(l, r);
        build(data, l, mid, rt<<1);
        build(data, mid+1, r, rt<<1|1);
        tree[rt] = tree[rt<<1|1] ^ tree[rt<<1];
    }

    void modify(int pos, int val, int l, int r, int rt){
        if(pos > r) return;
        if(l == r){
            tree[rt].set(val);
            return;
        }
        int mid = mid(l, r);
        if(pos <= mid) modify(pos, val, l, mid, rt<<1);
        else modify(pos, val, mid+1, r, rt<<1|1);
        tree[rt] = tree[rt<<1|1] ^ tree[rt<<1];
    }

    basis query(int ql, int qr, int l, int r, int rt){
        if(ql > qr) return basis();
        if(ql <= l && r <= qr) return tree[rt];
        int mid = mid(l, r);
        basis ret;
        if(ql <= mid) ret = query(ql, qr, l, mid, rt<<1);
        if(qr > mid) ret = ret ^ query(ql, qr, mid+1, r, rt<<1|1);
        return ret;
    }
}seg;

struct BIT{
    int val[maxn];
    BIT(){memset(val, 0, sizeof val);}
    void modify(int pos, int v, int n){
        for(int i=pos; i<=n; i+=(-i)&i) val[i] ^= v;
    }
    int query(int pos){
        int ret = 0;
        for(int i=pos; i>0; i-=(-i)&i) ret ^= val[i];
        return ret;
    }
}bit;

int a[maxn], b[maxn];

void solve(){
    int n, q, t, l, r, k;
    cin >> n >> q;
    for(int i=1; i<=n; i++) cin >> a[i];
    for(int i=2; i<=n; i++) b[i] = a[i-1] ^ a[i];
    seg.build(b, 1, n, 1);
    for(int i=0; i<q; i++){
        cin >> t;
        if(t == 1){
            cin >> l >> r >> k;
            bit.modify(l, k, n+1);
            bit.modify(r+1, k, n+1);
            seg.modify(l, k, 1, n, 1);
            seg.modify(r+1, k, 1, n, 1);
        }else{
            cin >> l >> r;
            int cnt=0, head = a[l] ^ bit.query(l);
            basis bas = seg.query(l+1, r, 1, n, 1);
            bas.add(head);
            cout << (1ll << (bas.count())) << '\n';
        }
    }
}

signed main(){
    Android;
    solve();
}