Codeforces Round #757 (Div. 2) C题

题意

有一个序列a，定义一个值c为a的所有子序列的异或和之和。现忘了序列a，但给出m条信息，关于一个区间[l,r]内所有元素或的值，保证a中所有元素都出现过，需要求值c。

思路

之所以整理这题，是因为它很有代表性，而且它的思想有许多可以学习的地方。
首先，异或和或都是位运算，所以可以从位的角度考虑。
如果n位全部都是0，结果显然是0；
如果n位中至少有1个1，那么结果是2^{n-1}。
证明：
至少有1个1时，任取1个1放到最后，那么前面的n-1位就有2^{n-1}种选法，结果是0或1。当结果是0时，取最后一位1；当结果是1时，最后一位不取。所以最后一位有一种选法使得结果是1，恰好是一半。
那么我们把给的所有限制条件或起来，得到的就是所有数是否至少出现过一次。把这个结果乘上2^{n-1}就是答案。

代码

#include <iostream>
#include <string>
#include <cstring>
#include <algorithm>
#include <queue>
#include <vector>
#include <set>
#include <stack>
#include <cmath>
#include <unordered_map>
using namespace std;
using ll = long long;
using PII = pair<ll, ll>;
const int maxn = 1e5 + 10;
const ll mod = 1e9 + 7;
ll power(ll a, ll b, ll mod)
{
    ll res = 1;
    while (b > 0)
    {
        if (b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
        b >>= 1;
    }
    return res;
}
int main()
{
    int t;
    cin >> t;
    while (t--)
    {
        int n, m;
        cin >> n >> m;
        int x, sum = 0;
        for (int i = 1; i <= m; i++)
        {
            scanf("%*d%*d%d", &x);
            sum =sum| x;
        }
        cout << sum * power(2, n - 1, mod) % mod << endl;
    }
    return 0;
}