【数学】【位运算】Divan and bitwise operations—CF1614C

Divan and bitwise operations—CF1614C
参考文章

思路

假设 $a$ 数组有 $k$ 个数的二进制第 $i$ 位上的数字是 $1$，那么 $a$ 数组中二进制第 $i$ 位对答案的贡献为：
$w=2^{i-1}\ast (C_k^1+C_k^3+C_k^5+...+C_k^{比k小的最大奇数})\ast C_k^{n-k}$。
其中，$2^{i-1}$ 表示二进制第 $i$ 位的权重；$(C_k^1+C_k^3+C_k^5+...+C_k^{比k小的最大奇数})$ 表示在 $k$ 个有序的 $1$ 排列中，有多少种选法能选出奇数个 $1$；$C_k^{n-k}$ 表示在 $n-k$ 个有序的 $0$ 排列中，有多少种选法。
因为
$(C_k^1+C_k^3+C_k^5+...+C_k^{比k小的最大奇数})=2^{k-1}$
所以
$w=2^{i-1}\ast 2^{n-1}$
我们可以看出：$a$ 中如果存在数在它的二进制第 $i$ 位是 $1$，那么第 $i$ 位的整体贡献就是定值 $2^{i-1}\ast 2^{n-1}$，与 $1$ 的个数无关。

所以我们现在的任务就变成了寻找一个数 $y$，使得 $x$ 中二进制每一位都是 $a$ 数组中二进制每一位的按位或，即 $y=a_1,a_2,a_3,...a_n的按位或$，这很容易做到，让 $y$ 与所有的 $x$ 按位或即可。

$Code$

#include 
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 2e5 + 10;
const int mod = 1e9 +7;

int n, m;

int qpow(int a, int b) {
	int res = 1;
	while (b) {
		if (b & 1) {
			res = res * a % mod;
		}
		a = a * a % mod;
		b >>= 1;
	}
	return res;
}

void solve() {
	cin >> n >> m;
	
	int y = 0;
	while (m --) {
		int l, r, x;
		cin >> l >> r >> x;
		y |= x;
	}
	
	cout << "          ";
	cout << y * qpow(2, n - 1) % mod << "\n";
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
	cin >> T; cin.get();
	while (T --) solve();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45