# CF C. Divan and bitwise operations 题解（位运算+组合数学）

原题链接.

对于某个长为n的序列，给你该序列若干个子段及其元素的或（这些子段必然完全覆盖整个序列），告诉你一定存在一个序列满足要求，现在让你构造出满足要求的任一个序列，求它的所有子序列的异或和之和。（只需输出异或和之和）

hint1：如果我们把整个序列构造出来，那么该如何求该序列所有子序列的异或和之和？
hint2：对于hint1，利用排列组合，按位考虑每一位对答案的贡献，可以求出子序列的异或和之和 。那么现在考虑本题能否、本题是否必须把整个序列构造出来？
hint3：对于hint2，发现本题较难构造出整个序列，这个时候可以选择猜一种构造方法，也可以选择直接求出答案。发现想要不构造而直接求出答案，最大的阻碍就是：不知道第i位是1的有几个数，该怎么办？
hint4：对于hint3，我们不妨设第i位是1的数有k个，构成集合A，那么第i位不是1而是0的数有n-k个，构成集合B，对答案的贡献为w。当k=0时，显然w=0；当k>0时，应该从集合A中选奇数个，从集合B中随便选，这样
w= 2 i − 1 ∗ ( C n 1 + C n 3 + . . . + C n n − 1 ) ∗ 2 n − k 2^{i-1}*(C^1_n+C^3_n+...+C^{n-1}_n)*2^{n-k} 2i−1∗(Cn1​+Cn3​+...+Cnn−1​)∗2n−k,n为偶数.
w= 2 i − 1 ∗ ( C n 1 + C n 3 + . . . + C n n ) ∗ 2 n − k 2^{i-1}*(C^1_n+C^3_n+...+C^n_n)*2^{n-k} 2i−1∗(Cn1​+Cn3​+...+Cnn​)∗2n−k,n为奇数.
不管怎样，结合二项式定理w= 2 i − 1 ∗ 2 n − 1 2^{i-1}*2^{n-1} 2i−1∗2n−1
发现只要有大于等于1个数第i位为1，对于答案的贡献是相同的!那么怎么求是否至少存在一个数第i位为1呢？这个只需把题目中给的子段的结果或起来，得到的数的每一位1都对应着至少一个数该位为1。

时间复杂度： O ( n ) O(n) O(n)

#include 
#include 
using namespace std;
 
typedef long long LL;
const int mod=1e9+7;
 
const int N=2e5+10;
LL power[N];
 
int main()
{
    int t;
    cin>>t;
    power[0]=1;
    for(int i=1;i<=2e5;i++)//预处理2的n次方模mod
        power[i]=((LL)power[i-1]*2)%mod;
 
    while(t--)
    {
 
        LL l,r,x;
        LL res=0;
        LL n,m;
        cin>>n>>m;
        while(m--)
        {
            cin>>l>>r>>x;
            res|=x;
        }
        cout<<((LL)res*power[n-1])%mod< 
4 收获 
1.按位考虑的思想
 2.二项式定理可得出
 
    
     
      
       
        (
       
       
        
         C
        
        
         n
        
        
         1
        
       
       
        +
       
       
        
         C
        
        
         n
        
        
         3
        
       
       
        +
       
       
        .
       
       
        .
       
       
        .
       
       
        +
       
       
        
         C
        
        
         n
        
        
         
          n
         
         
          −
         
         
          1
         
        
       
       
        )
       
      
      
       (C^1_n+C^3_n+...+C^{n-1}_n)
      
     
    (Cn1​+Cn3​+...+Cnn−1​),n为偶数.
 
    
     
      
       
        (
       
       
        
         C
        
        
         n
        
        
         1
        
       
       
        +
       
       
        
         C
        
        
         n
        
        
         3
        
       
       
        +
       
       
        .
       
       
        .
       
       
        .
       
       
        +
       
       
        
         C
        
        
         n
        
        
         n
        
       
       
        )
       
      
      
       (C^1_n+C^3_n+...+C^n_n)
      
     
    (Cn1​+Cn3​+...+Cnn​),n为奇数.
 两种情况下结果均为2的n-1次方
 3.猜