gpt4 book ai didi

「学习笔记」容斥原理

转载 作者:我是一只小鸟 更新时间:2023-06-03 22:31:22 26 4
gpt4 key购买 nike

引入

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

                        
                      

最后此篇关于「学习笔记」容斥原理的文章就讲到这里了,如果你想了解更多关于「学习笔记」容斥原理的内容请搜索CFSDN的文章或继续浏览相关文章,希望大家以后支持我的博客! 。

26 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com