容斥原理

https://en.wikipedia.org/wiki/Inclusion–exclusion_principle

参考题目

abc252_d

https://atcoder.jp/contests/abc252/tasks/abc252_d
输入一个长度为N的数组，从中选三个下标 i < j < k，且 a[i] a[j] a[k] 互不相同
问有多少种选法

参考代码

#include <bits/stdc++.h>
using namespace std;
int n, x;
int c[200020];
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> x;
		c[x]++;
	}
	long long z = n * (n - 1LL) * (n - 2) / 6;
	for (int i = 0; i < 200010; i++)
	{
		z -= c[i] * (c[i] - 1LL) * (c[i] - 2) / 6;
		z -= c[i] * (c[i] - 1LL) / 2 * (n - c[i]);
	}
	cout << z << endl;
	return 0;
}

题解

abc253_d FizzBuzz Sum Hard

https://atcoder.jp/contests/abc253/tasks/abc253_d
输入n和a和b
问1到n之间所有既不是a的倍数，也不是b的倍数的数字之和是多少？

参考代码

#include <bits/stdc++.h>
using namespace std;
long long n, a, b, c, z;
long long F(long long n)
{
	return n * (n + 1) / 2;
}
int main()
{
	cin >> n >> a >> b;
	c = a / __gcd(a, b) * b;
	z = F(n) - F(n / a) * a - F(n / b) * b + F(n / c) * c;
	cout << z << endl;
	return 0;
}

题解

输入n和a和b
问1到n之间所有既不是a的倍数，也不是b的倍数的数字之和是多少？

全部数字的和
减去a的倍数的和
减去b的倍数的和
加上既是a的倍数又是b的倍数之和

容斥原理

P5123 [USACO18DEC]Cowpatibility G

https://www.luogu.com.cn/problem/P5123

题目描述

研究证明，有一个因素在两头奶牛能否作为朋友和谐共处这方面比其他任何因素都来得重要——她们是不是喜欢同一种口味的冰激凌！

Farmer John 的 NN 头奶牛（2≤N≤5×1042\le N\le 5\times 10^4）各自列举了她们最喜欢的五种冰激凌口味的清单。为使这个清单更加精炼，每种可能的口味用一个不超过 10610^6 的正整数 ID\texttt{ID} 表示。如果两头奶牛的清单上有至少一种共同的冰激凌口味，那么她们可以和谐共处。

请求出不能和谐共处的奶牛的对数。

输入格式

输入的第一行包含 NN。以下 NN 行每行包含 55 个整数（各不相同），表示一头奶牛最喜欢的冰激凌口味。

输出格式

输出不能和谐共处的奶牛的对数。

样例 #1

样例输入 #1
4
1 2 3 4 5
1 2 3 10 8
10 9 8 7 6
50 60 70 80 90
样例输出 #1
4

提示

在这里，奶牛 44 不能和奶牛 11、22、33 中的任一头和谐共处，奶牛 11 和奶牛 33 也不能和谐共处。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ull;
map<ull, int> g[2];
int n, a[5];
long long z;
int main()
{
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			scanf("%d", &a[j]);
		}
		sort(a, a + 5);
		for (int j = 0; j < 32; j++)
		{
			ull r = 0;
			int c = 0;
			for (int k = 0; k < 5; k++)
			{
				if (j >> k & 1)
				{
					r = r * 1234567891 + a[k];
					c++;
				}
			}
			g[c & 1][r]++;
		}
	}
	for (pair<ull, int> i: g[0])
	{
		z += (long long)i.second * (i.second - 1) / 2;
	}
	for (pair<ull, int> i: g[1])
	{
		z -= (long long)i.second * (i.second - 1) / 2;
	}
	printf("%lld\n", z);
	return 0;
}

题解

https://www.luogu.com.cn/problem/P5123
http://www.usaco.org/index.php?page=viewproblem2&cpid=862

map<vector, int> g;

ans = n * (n - 1) / 2
for each set with size 1, S
if the number of i, such that S is a subset of A[i], is cnt
ans -= C(cnt, 2);

for each set with size 2, S
if the number of i, such that S is a subset of A[i], is cnt
ans += C(cnt, 2);

for each set with size 3, S
if the number of i, such that S is a subset of A[i], is cnt
ans -= C(cnt, 2);

for each set with size 4, S
if the number of i, such that S is a subset of A[i], is cnt
ans += C(cnt, 2);

for each set with size 5, S
if the number of i, such that S is a subset of A[i], is cnt
ans -= C(cnt, 2);

{1, 2, 3, 4, 5}
{1, 2, 3, 4, 5}

[A B C D E]
[A B C D E]

compute the pair of sets, whose intersection's size is exactly 1
size=0, +1, -0
size=1, -1, +1
size=2, +1, -2
size=3, -1, +3
size=4, +1, -4
size=5, -1, +5

[A, B]

+= 3 * 1
-= 3 * 2

[A, B, C]

  1. 容斥原理
    1. 参考题目
      1. abc252_d
      2. abc253_d FizzBuzz Sum Hard
      3. P5123 [USACO18DEC]Cowpatibility G
≡