引入
(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 |)
我总结了一句话
容斥原理,就是总共的减去重复的加上缺失的。
容斥原理的一般式
]
问题
有 (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\)
即
]
询问 (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
代码解释
num[a]
代表 (x^a) 这种形式的数被算了几次,很明显,我们希望最后每个 num
都为 (1),因此,我们需要加上少的或者减去多的。
int d = 1 - num[a];
ans += v * d;`
最后,我们再更新 num
。
for (int b = a; b
这段代码可以这么理解
假设我们计算 (x^2),我们会算到 (2^2、4^2、8^2 cdots),我们可以将它们转化一下,即 (2^2、2^4、2^6 cdots),因此,只要是指数是二的倍数的形式的数,我们都能算到。
真题
[春季测试 2023] 幂次
这道题对于 pow
有精度要求,要用 long double
,或者用 exp
,否则最后一个点过不去。
#include
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
服务器托管,北京服务器托管,服务器租用 http://www.fwqtg.net
机房租用,北京机房租用,IDC机房托管, http://www.fwqtg.net