线性基模板

线性基

可以解决如下问题：

给定一个集合S，包含若干个数 $a_1,a_2,\dots ,a_n$a1​,a2​,…,an​

1. 求S子集中所有元素异或和的最大值、最小值、第k小、第k大、所有子集异或之和。
2. 判断一个数是否可以被S某子集元素异或出来。

struct LinerBasis{
    ll p[64],rk,tot;
    //p集合中的元素是S的一组极大线性无关组
    //rk是秩,tot是插入元素的个数
    //1<<rk或者(1<<rk)-1就是不同异或和的种数
    LinerBasis(ll a[],int n){
        memset(p,0,sizeof(p));
        tot=rk=0;
        for(int i=0;i<n;++i)rk+=insert(a[i]);
        //能插入，则秩加一
    }
    void rebuild(){
        //将p从行阶梯矩阵通过行变换变成行简化阶梯矩阵
        int num=0;
        for(int i=0;i<=62;++i)if(p[i]){
            for(int j=i+1;j<=62;++j)
                if(p[j]&(1<<i))p[j]^=p[i];
            p[num++]=p[i];
        }
    }
    bool insert(ll x){
        ++tot;
        for(int i=62;i+1;--i)if(x>>i){
            if(!p[i]){
                p[i]=x;
                return 1;
            }
            x^=p[i];
        }
        return 0;
    }
    bool find(ll x){//判断一个数能不能被p线性表出
        for(int i=62;i+1;--i)if(x>>i){
            if(!p[i])return 1;
            x^=p[i];
        }
        return 0;
    }
    ll max_xor(){//先rebuild
        //子集最大异或和
        ll res=0;
        for(int i=0;i<rk;++i)
            if(p[i])res^=p[i];
        return res;
    }
    ll min_xor(){
        if(rk==tot)
        for(int i=0;i<=62;++i)if(p[i])return p[i];
        return 0;
        //若秩与总向量组的秩不同，就能异或出来0
        //考虑插入时，如果一个数不能插入
        //则它最终被p中已知的无关组异或成了0，所以最小值=0
    }
    ll sum(){
        //返回所有不同异或和的和
        //考虑每一位的贡献，若第i位是1，则有1<<(rk-1)种组合
        //若第i位为0，贡献为0
        ll res=0;
        for(int i=0;i<=62;++i)res|=p[i];
        return res<<(rk-1);
    }
    ll Kth_small_num(ll k){//先rebuild
    //第k小：先判断最小值是否为0，若为0，则k--,第一小要特判
        if(tot!=rk){
            if(k==1)return 0;
            k--;
        }
        if(k>(1ll<<rk)-1||k<0)return -1;
        ll res=0;
        for(int i=0;i<rk&&k;++i,k>>=1)
            if(k&1)res^=p[i];
        return res;
    }
};

Cut

给一棵树，定义图的割的权值是两个端点分别在S、T中的边的异或和，求所有可能权值的和
某个割的权值等价于与S集合中的点相连的边的异或和，假设a在集合S，因为若a->b有一条边，则b->a也有一条，当b也在S中时，异或和为0，当b不在S中时，异或和等于定义的权值。
套模板即可

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct LinerBasis{
    ll p[64],cnt;
    LinerBasis(ll a[],int n){
        memset(p,0,sizeof(p));
        cnt=0;
        for(int i=0;i<n;++i)cnt+=insert(a[i]);
    }
    bool insert(ll x){
        for(int i=62;i+1;--i)if(x>>i){
            if(!p[i]){
                p[i]=x;
                return 1;
            }
            x^=p[i];
        }
        return 0;
    }
    ll sum(){
        ll res=0;
        for(int i=0;i<=62;++i)res|=p[i];
        return res<<(cnt-1);
    }
};
ll a[100008];
int main(){
    ll n,m,x,y,v;
    scanf("%lld%lld",&n,&m);
    for(int i=0;i<m;++i){
        scanf("%lld%lld%lld",&x,&y,&v);
        a[x]^=v;
        a[y]^=v;
    }
    LinerBasis l(a,n);
    ll ans=l.sum();
    while(ans>1000000000)ans/=10;
    printf("%lld",ans);
}