2019 牛客多校 第一场 H、XOR

已知有  个数字 ，并且 ，求这个区间的所有异或和为  的子区间的长度和。

-----------------------------------------

1、异或和为0，肯定是线性基啊。

2、直接求出所有异或和为  子区间，再累加长度时间上肯定承受不了，所以我们考虑求出每个数字在异或和为0的子区间中出现的次数。

3、考虑先对原数组求一次线性基，设求出的线性基的秩为 ，然后对于所有的非基底元素，他的出现的次数就是 。

4、对于每个基底元素，我们用 非基底元素和其他的基底元素 再跑一个线性基出来，设这个线性基的秩为 ，然后判断这个数字能否成功插入到刚刚求到的线性基中，若可以，则这个数字的出现的次数是 

证明如下：https://www.cnblogs.com/cdcq/p/11211836.html

Code：

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN = 1e5 + 5;
const ll mod = 1e9 + 7;
ll a[MAXN];
ll c[100];
ll c1[100];
ll temp[100];
bool vis[MAXN];
ll power(ll a, ll b)
{
	ll res = 1;
	while (b)
	{
		if (b & 1)
			res = res * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}
bool insert(ll bas[], ll x)
{
	for (int i = 63; i >= 0; i--)
	{
		if (x & (1LL << i))
		{
			if (bas[i] == 0)
			{
				bas[i] = x;
				return true;
			}
			else
				x ^= bas[i];
		}
	}
	return false;
}
int main()
{
	int n;
	while (scanf("%d", &n) > 0)
	{
		vector<ll>v;//线性基里面的元素
		memset(c, 0, sizeof(c));
		memset(c1, 0, sizeof(c1));
		memset(vis, 0, sizeof(vis));
		int cnt = 0, cnt1 = 0;
		for (int i = 1; i <= n; i++)
		{
			scanf("%lld", &a[i]);
			if (insert(c, a[i]))
			{
				vis[i] = true;
				cnt++;
				v.push_back(a[i]);
			}
		}
		if (v.size() == n)
		{
			printf("0\n");
			continue;
		}
		ll res = (n - cnt) * power(2, n - cnt - 1) % mod;
		for (int i = 1; i <= n; i++)
		{
			if (vis[i] == false)
			{
				if (insert(c1, a[i]))
					cnt1++;
			}
		}
		//c1是非线性基元素的线性基
		int len = v.size();
		for (int i = 0; i < len; i++)//枚举每个元素
		{
			cnt = cnt1;
			for (int i = 0; i < 100; i++)
				temp[i] = c1[i];
			for (int j = 0; j < len; j++)
			{
				if (i != j)
				{
					if (insert(temp, v[j]))
						cnt++;
				}
			}
			if (!insert(temp, v[i]))
			{
				res += power(2, n - cnt - 1);
				if (res >= mod)
					res -= mod;
			}
		}
		printf("%lld\n", res % mod);
	}
}