题意
有一个序列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;
}
Comments | NOTHING