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

题目大意

有 $n$ 个非负整数 $a_{1,2,\ldots,n}$。

有 $m$ 个信息 $(l, r, x)$，每一组表示 $a_l \oplus a_{l+1} \oplus \cdots \oplus a_r = x$（保证所有数都被覆盖）。

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

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

思路

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

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

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

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

$$2^{A-1} \cdot 2^B = 2^{n-1}$$

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

所以，我们判断有哪一位至少出现过一次（对所有 $x$ 取 OR），然后加起来，乘以 $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;
}