CF1614C-Divan and bitwise operations

题目大意：一个数列的“舒适值”定义为这个数列中所有子序列的异或值之和。给出一个数列的某些子段所有数按位或的值，求这个数列的舒适值。

首先明确一点：一个长度为n的数列，子序列有$2^n-1$个，暴力找出所有子序列并运算显然不可取。

位运算中，每次运算位与位之间的数值不互相影响，所以尝试对每一位单独分析。假设整个数列中，第i位为1的数总共有x个。一个子序列中如果有奇数个元素的第i位为1，那么这个子序列的第i位最终的异或值的第i位就为1，否则这个子序列的第i位最终的异或值就为0。第i位为1的数总共有x个，那么第i位为0的数就有n-x个。取子序列的过程实际上相当于取出一些第i位为1的数和一些第i位为0的数并将他们组合起来。在n-k个第i位为0的数中取若干个出来的方法数是$2^{n-k}$。如果想要第i位对舒适值有贡献，需取出奇数个第i位为1的数，取法为$C_x^1+C_x^3+C_x^5+...+C_x^x$种。那么第i位对于舒适值所能做出的全部贡献就是

$(C_x^1+C_x^3+C_x^5+...+C_x^x) \times 2^i \times 2^{n-x}$

其中$2^i$指第i个二进制位的权。

其中，通过组合数的性质可以算出$C_x^1+C_x^3+C_x^5+...+C_x^x=2^{x-1}$，因此原式可化为

$2^{n-1} \times 2^i$

也就是说，舒适值实际上就是数列中的每一个元素的值都按位或的结果乘上$2^{n-1}$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

#include <bits/stdc++.h>
using namespace std;
const long long mod = 1e9 + 7;
long long ksm(long long a, long long x)
{
    long long ret = 1;
    while (x)
    {
        if (x & 1)
            ret = ret * a % mod;
        a = a * a % mod;
        x >>= 1;
    }
    return ret;
}
int main()
{
    int _, n, l, r, m;
    long long x, t;
    scanf("%d", &_);
    while (_--)
    {
        scanf("%d%d", &n, &m);
        t = 0;
        while (m--)
        {
            scanf("%d%d%lld", &l, &r, &x);
            t |= x;
        }
        printf("%lld\n", t * ksm(2, n - 1) % mod);
    }
    return 0;
}