Educational Codeforces Round 58 (Rated for Div. 2) G 线性基

https://codeforces.com/contest/1101/problem/G

题意

一个有n个数字的数组a[],将区间分成尽可能多段,使得段之间的相互组合异或和不等于零

题解

• 根据线性基的定义(线性无关),任意线性基组成的集合的异或和都不会等于0,因为假如等于零,说明一定存在一个基能被其他基异或表示
• 依次将数组a插入线性基中,最后非0线性基的数量就是答案

代码

#include<bits/stdc++.h>
#define ll long long 
#define M 200005
using namespace std;
ll a[M],sum=0,n,BS[50];
ll sol(){
    for(int i=1;i<=n;i++){
        for(int j=30;j>=0;j--){
            if(a[i]>>j&1){
                if(!BS[j]){BS[j]=a[i];break;}
                a[i]^=BS[j];
            }
        }
    }
    ll ans=0;
    for(int i=0;i<=30;i++)ans+=(BS[i]>0);
    return ans;
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        sum^=a[i];
    }
    if(sum==0)cout<<-1;
    else cout<<sol();
}

Educational Codeforces Round 58 (Rated for Div. 2) G 线性基

原文：https://www.cnblogs.com/VIrtu0s0/p/10631617.html