牛客月赛50 D 生日（计算贡献）

登录—专业IT笔试面试备考平台_牛客网牛客网是互联网求职神器，C++、Java、前端、产品、运营技能学习/备考/求职题库，在线进行百度阿里腾讯网易等互联网名企笔试面试模拟考试练习,和牛人一起讨论经典试题,全面提升你的技术能力https://ac.nowcoder.com/acm/contest/11227/D这是我第一次接触计算贡献答案的题目，教育意义很好。

首先我们来思考一下该题目有哪些人能够相互造成影响从而贡献出当天生日的属性异或值，很明显就只有第i天，第2*i天和第2*i+1天，最多3天能相互影响。

那么在第i天就有以下几种组合能够做出贡献

                                                                                                                                                                                    所以会产生    (a[i] ^ a[2 * i]) + (a[i] ^ a[2 * i + 1]) + (a[2 * i] ^ a[2 * i + 1]) + (a[i] ^ a[2 * i] ^ a[2 * i + 1])  的贡献值，但显然这只是一个方案中其中一天的贡献值，还有其他的天数，所以我们考虑在这种情况下其他天数选取的可能，有2的n-3次方那么多，乘上后即为该天对答案的贡献

当然我们还需要考虑一些特况，比如说上面的就是2i+1≤n的时候，当2i+1>n但2i<=n时，我们在第i天的组合明显就只有a[i]^a[2i+1]了，然后再乘上2的n-2次方即为最后对答案的贡献。

最后如果2*i也大于n了那么明显后面的天都不会对答案有贡献，所以直接break即可。

int n;
ll a[MAXN];
const int mod = 1e9 + 7;

ll q_pow(ll a, ll b) {
	ll rec = 1;
	while (b) {
		if (b & 1)
			rec = rec * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return rec;
}

int main() {
//	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++)
		scanf("%lld", a + i);
	ll base1 = q_pow(2, n - 3);
	ll base2 = q_pow(2, n - 2);
//	printf("%lld %lld\n", base1, base2);
	ll ans = 0;
	for (int i = 1; i <= n; i++) {
		if (2 * i + 1 <= n) {
			ans = (ans + base1 * ((a[i] ^ a[2 * i]) + (a[i] ^ a[2 * i + 1]) + (a[2 * i] ^ a[2 * i + 1]) +
			                      (a[i] ^ a[2 * i] ^ a[2 * i + 1]))
			       % mod) % mod;
		} else if (2 * i <= n) {
			ans = (ans + base2 * (a[i] ^ a[2 * i]) % mod) % mod;
		} else
			break;
	}
	printf("%lld", ans);
	return 0;
}