Divan and bitwise operations

题目大意

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

有$m$个信息$(l,r,x)$,每一组表示$a_l\oplus a_{l+1} \oplus … \oplus 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;
}

• 本文作者： 水蓝络合物
• 本文链接： https://miku39393939.github.io/2021/11/29/cf1614C/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！