「学习笔记」容斥原理

引入

(A_1)：学语文的人， (A_2)：学数学的人，(A_3)：学英语的人，(A_4)：学 OI 的人

(A_1 cap A_2)：同时学语数的人

(A_1 cup A_2)：学语文或数学的人

(left | A_1 cup A_2 right | = left | A_1 right | + left | A_2 right | - left | A_1 cap A_2 right |)

(left | A_1 cup A_2 cup A_3 right | = left | A_1 right | + left | A_2 right | + left | A_3 right | - left | A_1 cap A_2 right | - left | A_1 cap A_3 right | - left | A_2 cap A_3 right | + left | A_1 cap A_2 cap A_3 right |)

(left | A_1 cup A_2 cup A_3 cup A_4 right | = left | A_1 right | + left | A_2 right | + left | A_3 right | + left | A_4 right |\ - left | A_1 cap A_2 right | - left | A_1 cap A_3 right | - left | A_2 cap A_3 right | - left | A_1 cap A_4 right | - left | A_2 cap A_4 right | - left | A_3 cap A_4 right | \+ left | A_1 cap A_2 cap A_3 right | + left | A_1 cap A_2 cap A_4 right | + left | A_2 cap A_3 cap A_4 right | \- left | A_1 cap A_2 cap A_3 cap A_4 right |)

---

我总结了一句话

容斥原理，就是总共的减去重复的加上缺失的。

容斥原理的一般式

[sum_{b subseteq left lbrace A_1, A_2, cdots, A_n right rbrace } (-1) ^ {left| B right | + 1} cdot left | bigcap_{a_i in B}A_i right | ]

问题

有 (n) 对夫妻坐成一圈，每对夫妻不能坐在一起，问方案数。

总的方案数为 (dfrac{2n!}{2n} = (2n - 1)!)
我们将夫妻绑定在一起，这样，这对夫妻可以看作是一个人。
来计算不合法方案数：
一对夫妻坐在一起时，方案数为 ((2n - 2)!)，在 (n) 对夫妻中选一堆绑定，并且夫妻之间也有坐的顺序，因此一对夫妻坐在一起的非法方案数为 (2 cdot C(n, 1) cdot (2n - 2)!)。
但是，在这一对夫妻坐在一起的方案数中，包含了两对夫妻坐在一起、三对夫妻坐在一起的情况，因此，有重复计算的，两对夫妻坐在一起被计算了两次，三对夫妻坐在一起被计算了三次。
我们要减去两对夫妻坐在一起的情况的方案数，即 (2^2 cdot C(n, 2) cdot (2n - 3)!)，在这两对夫妻坐在一起的情况里，同样，也包含了三对夫妻坐在一起的情况，而这一减，三对夫妻坐在一起的方案数直接变为 (0) 了，因此我们需要再把他们加上。
由此，就能够看出有容斥的规律了，我们往后推，减去四对夫妻坐在一起的方案数，加上 (5) 对夫妻坐在一起的方案数。。。
因此，总的非法方案数就是 (2 cdot C(n, 1) cdot (2n - 2)! - C(n, 2) cdot (2n - 3)! cdot 2^2 + C(n, 3) cdot (2n - 4)! cdot 2^3 cdots)
总的方案数减去非法方案数就是 ((2n - 1)! - 2 cdot C(n, 1) cdot (2n - 2)! + C(n, 2) cdot (2n - 3)! cdot 2^2 - C(n, 3) cdot (2n - 4)! cdot 2^3 cdots\)
即

[sum_{i = 0}^n C(n, i) cdot (2n - i - 1)! cdot 2^i cdot (-1) ^ i ]

---

询问 (1 - n) 中有多少个数可以表示为 (x^y)，(y > 1) 的形式。(left (n le 10^{18} right ))

由于 long long 的范围可知，可行的 (y) 小于等于 (64)。
在这 (n) 个数中，能表示成 (x^2) 的数有 (sqrt{n}) 个，能表示成 (x^3) 的数有 (sqrt[3]{n}) 个，能表示成 (x^y) 的数有 (sqrt[y]{n}) 个。
但是，我们的答案就是 (sum_{i = 2}^{y}sqrt[i]{n}) 吗？
很明显，不是。
看一看这种情况，(y^6 = (y^3)^2 = (y^2)^3)，很明显，直接求和会有重复，因此，我们要减去重复的部分

cin >> n; for (int a = 2; a <= 64; ++ a) {     num[a] = 0; // num[a] 代表 x^a 这种形式的数被算了几次 } for (int a = 2; a <= 64; ++ a) { // 算 x^a 这种形式的数有多少个     ll v = floor(pow(n, (long double)1.0 / a)) - 1; //  ll v = (ll)floor(exp(log(n) / a)) - 1;     int d = 1 - num[a];     ans += v * d;     for (int b = a; b <= 64; b += a) {         num[b] += d;     } } 

代码解释

num[a] 代表 (x^a) 这种形式的数被算了几次，很明显，我们希望最后每个 num 都为 (1)，因此，我们需要加上少的或者减去多的。

int d = 1 - num[a]; ans += v * d;` 

最后，我们再更新 num。

for (int b = a; b <= 64; b += a) { 	num[b] += d; } 

这段代码可以这么理解
假设我们计算 (x^2)，我们会算到 (2^2、4^2、8^2 cdots)，我们可以将它们转化一下，即 (2^2、2^4、2^6 cdots)，因此，只要是指数是二的倍数的形式的数，我们都能算到。

真题

[春季测试 2023] 幂次
这道题对于 pow 有精度要求，要用 long double，或者用 exp，否则最后一个点过不去。

#include <bits/stdc++.h> using namespace std; typedef long long ll;  ll n, k, ans; ll num[70];  int main() { 	ios::sync_with_stdio(false); 	cin.tie(0),	cout.tie(0); 	cin >> n >> k; 	for (int a = k; a <= 64; ++ a) { 		num[a] = 0; 	} 	for (int a = k; a <= 64; ++ a) { 		ll v = floor(pow(n, (long double)1.0 / a)) - 1; //		ll v = (ll)floor(exp(log(n) / a)) - 1; 		ll d = 1 - num[a]; 		ans += v * d; 		for (int b = a; b <= 64; b += a) { 			num[b] += d; 		} 	} 	cout << ans + 1 << 'n'; 	return 0; }