【CF#757 (Div. 2)】C. Divan and bitwise operations

【CF#757 (Div. 2)】C. Divan and bitwise operations

对按位运算特别的不会（），所有来写写题解

Divan and bitwise operations

传送门

题意：
首先知道序列的舒适值：所有的子序列的异或值相加。
输入给出：
1）序列长为n，其中的值是1-n，位置不定。
2）给出m组的l-r的或。
要求输出该序列的舒适值。

题解：
首先异或：同为1，不同为0
现在来看原序列：
对于第i位——我们假设此位有k个1，那0的个数为n-k
那么，我们每次只要选择奇数个1，而0随意，就能保证此处为1。
那么这个位置对于舒适度的贡献就是：（所有奇数次的1出现的情况）*2n-1-k*2i
【需要知道，奇数个1的出现情况=偶数个1的出现情况，而他们的和是2k，那么，奇数个k的出现情况必然是2k-1】
那么第i位贡献的舒适值就可以表示为2k-1*2n-k *2i
化简可以消去k，即为：2n-1 *2i
也就是直接2n-1 OR(原序列)=2n-1 OR(m组的l-r的或)

代码：

#include 
using namespace std;
const int maxn=2e5+7;;
#define ll long long
#define sc scanf
#define pr printf
const ll mod=1e9+7;
ll p=mod;
ll fastPower(ll x, ll n) {
       ll res = 1;
       x%=p;
       while (n){
           if(n & 1)  res = (res * x )%p;
           n >>= 1;
           x = (x * x)%p ;
       }
       return res;
    }
int main()
{
     int t;sc("%d",&t);
    int n,m,l,r;
    while(t--){
        sc("%d%d",&n,&m);
        ll an=0;
        int a,b;ll c;
        while(m--){
        	sc("%d%d%lld",&a,&b,&c);
        	an=(an|c);
		}
		pr("%dn",fastPower(2,n-1)*an%mod);
 
    }
    return 0;
}

题外话：
如果你没注意到化简后和k无关，其实也是能做的。
把序列里的每一个值给确定（用一个set，排序，我们以出现的最小的或值为它本位的值，确定完了后就从set中删除）。
然后统计它每一位1，0的个数。
然后按照公式计算相加。