【Educational Codeforces Round 58 (Rated for Div. 2) G. (Zero XOR Subset)-less】前缀异或和+线性基

G. (Zero XOR Subset)-less

题意

题意就是给你一个长度为n的序列每个数的大小为a[i]
要求把序列分为多个连续的段，保证分完之后,
无论选取那些段相异或答案都不是0，问最多可以分为多少段。

$1<=n<=2?10^5$
$0<=a_i<=10^9$
做法

首先由于答案要求是连续的段，而每一段的异或和是一个值，这个值刚好可以通过两个前缀异或和异或值得到，那么每一段的值就转换为前缀异或和，那么问题就变成，给你n个值，让你在其中选出尽量多的值，保证这些值任意组合异或和都不为0.这就变成线性基的经典问题。直接构造出n个前缀异或和的线性基，基底的个数便是答案。

代码

#include<stdio.h>
int p[65];
int main()
{
    int n,x,now=0;scanf("%d",&n);for(int i=0;i<n;i++){
    scanf("%d",&x);now=now^x;x=now;for(int j=31;j>=0;j--){
    if(x&(1<<j)){
    if(!p[j]){
    p[j]=x;break;}else x=x^p[j];}}}if(now==0){
    printf("-1\n");return 0;}int ans=0;for(int i=31;i>=0;i--) if(p[i]) ans++;printf("%d\n",ans);return 0;
}