【codeforces 757 Div2 C】1614/C Divan and bitwise operations题解

题目大意

有$n$个非负整数$a_{1,2,...n}$

有$m$个信息$(l,r,x)$,每一组表示$a_l?a_{l+1}?...?a_r=x$ (保证所有数都被覆盖)

求数组$a$的所有子序列异或和的和。(有多种$a$数组的组成话,任意输出一种情况下的和即可)

结果对$10^9+7$取模

思路

通常这种异或和的题大概率是要按位进行计算

假设$a$数组中第$y$位上为$1$的数有$A$个,那么为了让它们在这一位异或和为$1$,我们要从中任意选出奇数个，方案数有:

$C_A^1+C_A^3+...+C_A^{(A\&1)?A:A?1}=2^{A?1}$,

假设剩下这一位为$0$的数有$B$个,那它们可以任意选取,共有$2^B$种方案数,所以总方案数为

$2^{A?1}?2^B=2^{n?1}$

可见,某一位提供的方案数,与这一位是$1$的数的个数无关,只要这一位是$1$的数至少有$1$个,那么它提供的方案数就是$2^{n?1}$。如果它是第$k$位,那它的贡献就是$2^{k?1}?2^{n?1}$

所以,我们判断有哪一位至少出现过一次,然后加起来,乘以$2^{n?1}$,就是最终的答案了。

代码

#include <cstdio>
#include <iostream>
using namespace std;const int maxN = 2e5 + 7;
const long long Mod = 1e9 + 7;int T, n, m;long long quickPow(long long a, long long b, long long c)
{
    long long tmp = a, ans = 1;while(b) {
    if(b & 1)ans = ans * tmp % c;tmp = tmp * tmp % c;  b >>= 1;  }return ans;
}int main()
{
    scanf("%d", &T);while(T--) {
    scanf("%d%d", &n, &m);long long ans = 0;for(int i = 1; i <= m; ++i) {
    long long l, r, x;scanf("%lld%lld%lld", &l, &r, &x);ans |= x;}printf("%lld\n", ans * quickPow(2, n - 1, Mod) % Mod);}return 0;
}