「學習筆記」容斥原理

引入

\(A_1\)：學語文的人， \(A_2\)：學數學的人，\(A_3\)：學英語的人，\(A_4\)：學 OI 的人

\(A_1 \cap A_2\)：同時學語數的人

\(A_1 \cup A_2\)：學語文或數學的人

我總結了一句話

容斥原理，就是總共的減去重複的加上缺失的。

容斥原理的一般式

\[\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;
}