题目

给定 \(n\) 个 \(k\) 位二进制数，\(n\leq 2*10^5,k\leq 30\)

可以选择若干数将其所有二进制位取反，

最多可以有多少个区间的异或和不为 0

分析

考虑将区间异或和改成前缀异或和的异或，

那么每次就是让与前面重复的异或值个数尽量小，

可以用哈希维护

代码

#include 
#include 
#include 
#include 
#define rr register
using namespace std;
typedef long long lll;
const int N=100011,p=600011;
int n,a[N],b[N],al,sum; lll ans;
inline signed iut(){
	rr int ans=0; rr char c=getchar();
	while (!isdigit(c)) c=getchar();
	while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
	return ans;
}
struct Linked_Hash{
	struct node{int y,w,next;}E[p]; int Et,hs[p];
	inline void Clear(){Et=0,memset(hs,-1,sizeof(hs));}
	inline void Insert(int w,int x){E[++Et]=(node){x,w,hs[w%p]},hs[w%p]=Et;}
	inline signed locate(int W){
		for (rr int i=hs[W%p];~i;i=E[i].next)
		    if (E[i].w==W) return i;
		return -1;
	}
}H;
signed main(){
	n=iut(),H.Clear(),H.Insert(0,1),
	al=(1<