CF1614C Divan and bitwise operations
题目描述
有一次，Divan 分析了一个由 n 个非负整数组成的序列 a_1, a_2, \ldots, a_n。他对该序列的每一个非空子序列，计算其所有元素的按位异或（bitwise XOR），并将所有异或值相加，得到该序列的“舒适度”（coziness）。
如果序列 c 可以通过从序列 d 中删除若干（可能为零或全部）元素得到，则称 c 是 d 的一个子序列。例如，[1,\,2,\,3,\,4]、[2,\,4] 和 [2] 都是 [1,\,2,\,3,\,4] 的子序列，但 [4,\,3] 和 [0] 不是。
Divan 对自己的分析非常自豪，但现在他丢失了序列 a，也忘记了舒适度的值！不过，Divan 还记得关于序列 a 的 m 个连续子段的按位或（bitwise OR）值。并且，原序列的每个元素都至少包含在这 m 个区间中的某一个。
Divan 请你帮忙，根据他记得的信息，计算出序列 a 的舒适度。如果可能有多个舒适度值，输出任意一个即可。
由于结果可能非常大，请输出对 10^9+7 取模后的值。
输入格式
第一行包含一个整数 t（1 \le t \le 10^3），表示测试用例的数量。
每个测试用例的第一行包含两个整数 n 和 m（1 \le n, m \le 2 \times 10^5），分别表示序列的长度和已知的连续区间数量。
接下来的 m 行，每行描述一个区间，包含三个整数 l、r、x（1 \le l \le r \le n，0 \le x \le 2^{30} – 1），表示区间 [l, r] 的按位或值为 x。
保证每个序列元素至少被包含在某一个区间内。保证一定存在满足所有条件的序列。
保证所有测试用例中 n 的总和与 m 的总和不超过 2 \times 10^5。
输出格式
对于每个测试用例，输出任意一个满足条件的序列 a 的舒适度，对 10^9+7 取模后的值。
输入输出样例 #1
输入 #1
3
2 1
1 2 2
3 2
1 3 5
2 3 5
5 4
1 2 7
3 3 7
4 4 0
4 5 2
输出 #1
4
20
112
说明/提示
在第一个样例中，满足条件的序列之一是 [0, 2]。考虑它所有的非空子序列：
- [0]：该子序列的按位异或为 0；
- [2]：该子序列的按位异或为 2；
- [0, 2]：该子序列的按位异或为 2。
所有结果之和为 4，所以答案为 4。
在第二个样例中，满足条件的序列之一是 [0,\,5,\,5]。
在第三个样例中，满足条件的序列之一是 [5,\,6,\,7,\,0,\,2]。
由 ChatGPT 4.1 翻译
思路
1. 为什么“每一位单独分析”？
在处理异或（XOR）、或（OR）等位运算题目时，不同二进制位之间是没有任何进位、借位相互影响的。因此，解题的最优策略通常是拆位计算。我们将原数组中的每个数字看作完全独立的二进制位（题目数据范围到 2^{30}-1，即最多 30 位），然后只盯着其中某一个特定的位去推导。
2. 子序列在什么情况下，该位对答案有贡献？
题解中说：“若 sum(1)%2=1 时该位才对答案有贡献”。
- 异或的本质规则：相同为 0，不同为 1。多个数一起异或时，只有当 1 的个数为奇数时，结果的这一位才是 1；如果有偶数个 1，异或结果就是 0。
- 因此，对于某一个特定的二进制位，我们只需要从原序列中挑出奇数个 1，再搭配上任意个 0，组成的子序列在这一位上的异或结果就是 1。只有结果为 1，才会对最终的“舒适度”数值产生贡献。
3. 最难懂的一步：组合数学推导公式
题解直接给出了公式：
2^{n-x} \cdot (\sum_{k=0}^{2k+1 \le x} C_x^{2k+1}) = 2^{n-1}
它的推导逻辑如下：
假设在长度为 n 的原序列中，当前观察的这一位上，总共有 x 个 1，那么剩下的 n-x 个数在这一位上必定都是 0。
- 选 1 的方案数：我们需要从这 x 个 1 中选出奇数个（1个、3个、5个……）。在组合数学中，根据二项式定理，从 x 个元素中选出奇数个元素的组合数之和，永远等于总子集数的一半： \sum_{k=0}^{2k+1 \le x} C_x^{2k+1} = 2^{x-1}
- 选 0 的方案数：0 无论怎么异或都不会改变结果。所以这 n-x 个 0，每个都有“选入子序列”或“不选入”两种状态，方案数为 2^{n-x}。
- 乘法原理合并：将两者相乘： 2^{x-1} \times 2^{n-x} = 2^{n-1}
这个结论非常重要：只要这一位上至少存在一个 1（即 x > 0），不管 1 的具体数量是多少，能让子序列异或结果为 1 的子序列总数，永远都是固定的 2^{n-1} 个。
4. 为什么答案是全局或和乘以 2^{n-1}？
既然每一位只要存在 1，它对答案产生贡献的次数就固定是 2^{n-1} 次。
那么问题就变成了：到底哪些位上存在 1？
- 题目给出了 m 个区间的按位或（OR）值。因为所有区间覆盖了整个数组，把这 m 个区间的值再全部“或”起来，等价于把原数组所有的数字全部“或”起来（即全局或和 S）。
- 全局或和 S 的某一位如果是 1，就意味着原数组在这一位上至少有一个数字是 1。
- 因此，S 本身就代表了所有有效位的值的总和。将其整体乘以出现次数 2^{n-1}，就是最终的答案： \text{Coziness} = S \times 2^{n-1} \pmod{10^9+7}
代码
const int mod=1000000007;
int qpow(int base,int exp){
int res=1;
base%=mod;
while(exp){
if(exp&1) res=(res*base)%mod;
base=(base*base)%mod;
exp/=2;
}
return res;
}
void solve() {
int n,m;
cin>>n>>m;
int ans=0;
while(m--){
int l,r,x;
cin>>l>>r>>x;
ans|=x;
}
cout<<(ans*qpow(2,n-1))%mod<<endl;
}
