Codeforces Round #757 (Div. 2) C题

发布于 2021-12-09  398 次阅读


题意

有一个序列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;
}

盛夏日落迟 灯火未夜匆匆明