C. Divan and bitwise operations

题意

已知序列长度为$n$，定义序列舒适度$coziness$为序列所有子集的异或和的总和。给出$m$个区间$[l,r]$ ，以及这个区间的 或值，现在求出满足区间限制的序列的任意一个可能的舒适度 $coziness$ 。

分析

根据题意这是一个不知道初始区间的序列，那么我们可以通过构造一个序列，使得其满足题目限定。容易发现题目中有$m$个区间，那么我们只要初始化每个区间中的一个元素，使得其等于该区间的$OR$值并且剩下元素全部为$0$即可满足题目要求。那么该序列就转化成了一个长度为$n$，其中若干个是题目要求$OR$值的数，剩下位全部为0的序列。那么我们接下去如何求其所有子序列的XOR的值的和呢(本题难点)？，我们针对每一位进行分析(因为在位运算XOR中每一位是独立的)，我们分析任意的一位，该位上有$n$个数，分别是构造序列上每一位上的数转化为二进制形式在当前二进制位上拥有的值，是0或者是1，那么我们可以设总共有$a$个$1$和$b$个$0$，然后我们可以发现想要对本题答案产生贡献，那么我们选择1的个数务必是奇数个，所以我们可以推出选奇数个1的方案数量式子：$C_a^1 + C_a^3 + C_a^5 + … =2^{a-1}$ 个，剩下的0根据二项式定理求得方案数为 $2^{b}$ 个。所以总共的方案数为$2^{b} * 2^{a-1} = 2^{a+b-1} = 2^{n-1}$。可以发现此时$a$和$b$是多少并不影响答案，因此我们只需要将所有二进制位数中出现过$1$的数扫一遍加起来即可。那么我们一开始需要一个操作就是将所有要求的$OR$值$OR$一遍，用一个数存下来。

• 参考代码：

#include<bits/stdc++.h>
using namespace std;
#define snow ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define re register int
#define int long long 
#define fer(i,a,b) for(re i = a ; i <= b ; i ++)
#define der(i,a,b) for(re i = a ; i >= b ; i --)
#define lowbit(x) (x&-x)
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int lcm(int a,int b){return a*b/gcd(a,b);}
typedef pair<int,int>PII;
typedef pair<int,string>PIS;
int n,m;
const int mod=1e9+7;
void solve(){
    cin>>n>>m;
    int gg=0;//存所有要求OR值OR一遍
    while(m--){
        int l,r,x;
        cin>>l>>r>>x;
        gg|=x;
    }
    int n2=1;
    for(int i=1;i<=n-1;i++){
        n2=n2*2%mod;
    }
    cout<<(n2*gg%mod)<<endl;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}