「学习笔记」容斥原理 - yi_fan0305

「学习笔记」容斥原理 - yi_fan0305 - 博客园

A1A1：学语文的人， A2A2：学数学的人，A3A3：学英语的人，A4A4：学 OI 的人

A1∩A2A1∩A2：同时学语数的人

A1∪A2A1∪A2：学语文或数学的人

|A1∪A2|=|A1|+|A2|−|A1∩A2||A1∪A2|=|A1|+|A2|−|A1∩A2|

|A1∪A2∪A3|=|A1|+|A2|+|A3|−|A1∩A2|−|A1∩A3|−|A2∩A3|+|A1∩A2∩A3||A1∪A2∪A3|=|A1|+|A2|+|A3|−|A1∩A2|−|A1∩A3|−|A2∩A3|+|A1∩A2∩A3|

|A1∪A2∪A3∪A4|=|A1|+|A2|+|A3|+|A4|−|A1∩A2|−|A1∩A3|−|A2∩A3|−|A1∩A4|−|A2∩A4|−|A3∩A4|+|A1∩A2∩A3|+|A1∩A2∩A4|+|A2∩A3∩A4|−|A1∩A2∩A3∩A4||A1∪A2∪A3∪A4|=|A1|+|A2|+|A3|+|A4|−|A1∩A2|−|A1∩A3|−|A2∩A3|−|A1∩A4|−|A2∩A4|−|A3∩A4|+|A1∩A2∩A3|+|A1∩A2∩A4|+|A2∩A3∩A4|−|A1∩A2∩A3∩A4|

我总结了一句话

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

容斥原理的一般式

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

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

询问 1−n1−n 中有多少个数可以表示为 xyxy，y>1y>1 的形式。(n≤1018)(n≤1018)

由于 long long 的范围可知，可行的 yy 小于等于 6464。
在这 nn 个数中，能表示成 x2x2 的数有 n−−√n 个，能表示成 x3x3 的数有 n−−√3n3 个，能表示成 xyxy 的数有 n−−√yny 个。
但是，我们的答案就是 ∑yi=2n−−√i∑i=2yni 吗？
很明显，不是。
看一看这种情况，y6=(y3)2=(y2)3y6=(y3)2=(y2)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] 代表 xaxa 这种形式的数被算了几次，很明显，我们希望最后每个 num 都为 11，因此，我们需要加上少的或者减去多的。

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

最后，我们再更新 num。

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

这段代码可以这么理解
假设我们计算 x2x2，我们会算到 22、42、82⋯22、42、82⋯，我们可以将它们转化一下，即 22、24、26⋯22、24、26⋯，因此，只要是指数是二的倍数的形式的数，我们都能算到。

[春季测试 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;
}

__EOF__