CF 1614C - Divan and bitwise operations

题目链接：

https://codeforces.com/contest/1614/problem/C

题目大意：

\(t\) 组测试，每组测试有一个长度为 \(n\) 的序列（序列元素未知），只知道序列中 \(m\) 个区间中区间元素位或的值，每个区间的左端点为 \(l\) ，右端点为 \(r\)，区间所有元素位或的值为 \(x\)，求序列所有子序列的 位异或的值之和，最后结果对 \(10^9\) + 7 取模。

思路：

参考：https://codeforces.com/blog/entry/97283

序列不定，求出任意一种结果就行，所以不考虑构造这个序列，而是去考虑序列性质。

求解一个序列所有子序列位异或的总和，可以先从序列中所有元素二进制的每一位被记入最后答案的总次数入手。

若一个序列中所有元素二进制第 \(i\) 位的值为 1 的数量是偶数，显然，这个序列位异或之后答案为 0，不用考虑。
如果数量是奇数，考虑到 1 XOR 0 = 1，我们可以将序列中的数字分成两个集合 \(A\) 和 \(B\)。
序列 \(A\) 中的数第 \(i\) 位为 0，那么在 \(A\) 中选数，使其异或和为 0 的组合方式总共有 \(2^{\lvert A \rvert}\) 种。
而序列 \(B\) 中由于第 \(i\) 位的值为 1，要使其与序列 \(A\) 中的数 \(XOR\) 的结果是 1，我们得选 奇数个 \(B\) 中的数字才能使异或后的第 \(i\) 位结果为 1，总的组合方式有 \(C_{\lvert B \rvert}^1\) + \(C_{\lvert B \rvert}^3\) + ... + \(C_{\lvert B \rvert}^{\lvert B \rvert - k}\) = \(2 ^ {\lvert B \rvert - 1}\) 种，其中当 \(\lvert B \rvert\) 为偶数时，\(k\) = 1，奇数时，\(k\) = 0。
所以某个序列的所有子序列第 \(i\) 位的位异或总和应该为 \(2 ^ {\lvert A \rvert}\) * \(2 ^ {\lvert B \rvert - 1}\) = \(2 ^ {n - 1}\)

题目中给出了序列某段区间的位或值\(x\)，将其全部按位或，得到这个序列按位取或的结果 \(ans\)，即这个序列所有元素二进制第 \(i\) 位的值已知，那么最终答案就是 ans * \(2 ^ {n - 1}\)。

代码：

#include 
using namespace std;
#define LL long long
const int mod = 1e9 + 7;
LL t, n, m, x, p;
LL PowerMod(LL a, LL b){
	if (b == 0) return 1;
	LL ans = 1;
	while (b != 0){
		if (b & 1) ans = (ans * a) % mod;
		b >>= 1;
		a = (a * a) % mod;
	}
	return ans;
}
void solve(){
	scanf("%lld%lld", &n, &m);
	p = PowerMod(2LL, n - 1);
	LL ans = 0;
	for (int i = 1; i <= m; i++){
		scanf("%lld%lld%lld", &x, &x, &x);
		ans |= x;
	}
	cout << (ans * p) % mod << "\n";
}
int main(){
	cin >> t;
	while (t--)
		solve();
	return 0;
}