题解：CF1101G (Zero XOR Subset)-less

fish_love_cat · 2026-04-26 15:36:07 · 题解

异或连续段，考虑转成前缀异或来做。

把每个前缀异或插在线性基里，如果插不进去就说明能被基里的数表示，若保留则会异或出 0 所以得扔掉。

保留在基里的数可以作为一段的结尾使用，于是答案就是线性基大小。

如果全部选择的结果是 0 那么显然无解，特判即可。

#include<bits/stdc++.h>
using namespace std;
const int MB=60;
int p[MB+5],sum;
void ins(int x){
    for(int i=MB;i>=0;i--)
    if((1ll<<i)&x){
        if(!p[i]){p[i]=x,sum++;return;}
        else x^=p[i];
    }
}
int main(){
    int n;
    cin>>n;
    int flc=0;
    for(int i=1;i<=n;i++){
        int x;
        cin>>x;
        flc^=x;
        ins(flc);
    }
    if(flc)cout<<sum;
    else cout<<-1;
    return 0;
}
// 些微的乡愁刺痛内心。
// 忘了是什么时候，她也曾在妖精仓库仰望这般星空。
// 姐妹们争先恐后地挤到屋顶，想要从高处欣赏如此景致。
// 虽然好像因为某个意外而被打断了（她记不太清楚），但就算是短短的片刻，大家一起仰望星空的情景直到现在依然历历在目。