容斥原理
可在离散数学(左孝凌)课本 p97 找到容斥原理的证明。容斥原理又叫包含排斥原理。
有三个集合时的公式如下:
∣S1∪S2∪S2∣=∣S1∣+∣S2∣+∣S3∣−∣S1∩S2∣−∣S1∩S3∣−∣S2∩S3∣+∣S1∩S2∩S3∣
组合恒等式:Cn0+Cn1+Cn2+⋯+Cnn=2n
容斥原理公式中一共有 2n−1 项,所以使用容斥原理计算一组集合的并集中元素个数的时间复杂度为 O(2n),n 为集合数量。
能被整除的数
枚举子集一般使用位运算。每一位代表选或不选一个元素。从 0 一直枚举到 2n−1 这些数字可以表示 n 个元素的子集的情况。本题不需要考虑一个都不选的情况,从 1 开始枚举。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36
| #include <iostream> using namespace std; typedef long long LL; int n, m; int p[20]; int main() { cin >> n >> m; for(int i=0;i<m;i++) { cin >> p[i]; } int res = 0; for(int i=1; i < 1 << m; i++) { int t = 1, cnt = 0; for(int j=0; j<m; j++) { if(i >> j & 1) { cnt ++; if((LL)t * p[j] > n) { t = -1; break; } t *= p[j]; } } if(t!=-1) { if(cnt % 2) res += n/t; else res -= n/t; } } cout << res << endl; return 0; }
|
Nim 游戏
给定 n 堆石子,两位玩家轮流操作,每次操作可以从任意一堆石子中拿走任意数量的石子(可以拿完,但不能不拿),最后无法进行操作的人视为失败。
问如果两人都采用最优策略,先手是否必胜。
假设有 n 堆石子,每堆石子有 ai 块石头。
如果 a1⊕a2⊕a3⊕⋯⊕an=0 那么先手必败。
如果 a1⊕a2⊕a3⊕⋯⊕an=0 那么先手必胜。
证明:
0⊕0⊕0⊕⋯⊕0=0
a1⊕a2⊕a3⊕⋯⊕an=x
设 x 的二进制表示中,最高位在第 k 位,那么 a1 an 中一定有 ai,其二进制表示中第 k 位的值为 1。
因为 ai⊕x<x,可以从 ai 中拿走 ai−(ai⊕x) 个石子,即将 ai 变成 (ai⊕x)。
a1⊕a2⊕a3⊕⋯⊕an
=a1⊕a2⊕a3⊕⋯⊕ai⊕x⊕ai+1⊕⋯⊕an
=x⊕x
=0
到此可以证明,如果 a1⊕a2⊕a3⊕⋯⊕an=0,一定存在一种操作方式,操作之后使 a1⊕a2⊕a3⊕⋯⊕an=0
接下来证明当 a1⊕a2⊕a3⊕⋯⊕an=0 时,无论如何操作,都会使得 a1⊕a2⊕a3⊕⋯⊕an=0
使用反证法,假设从 ai 中拿一些石子,使其变成 ai′,而 a1⊕a2⊕a3⊕⋯⊕ai′⊕ai+1⊕⋯⊕an=0
将两式上下进行异或
a1⊕a2⊕a3⊕⋯⊕ai′⊕ai+1⊕⋯⊕an=0
a1⊕a2⊕a3⊕⋯⊕ai⊕ai+1⊕⋯⊕an=0
可以得到:ai⊕ai′=0 即 ai=ai′,与题设矛盾。
Nim 游戏
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
| #include <iostream> using namespace std;
int main() { int n; scanf("%d", &n); int res; while(n--) { int x; scanf("%d", &x); res ^= x; } if(res) puts("Yes"); else puts("No"); return 0; }
|
Mex 运算
设 S 表示一个非负整数集合,定义 mex(S) 为求出不属于集合 S 的最小非负数整数的运算,即:mex(S) = { min(x) | x 属于自然数且 x 不属于 S }
SG 函数
在有向图游戏中,对于每个节点 x,设从 x 出发共有 k 条有向边,分别到达节点 y1, y2, …, yk,定义 SG(x) 为 x 的后继节点 y1, y2, …, yk 的 SG 函数值构成的集合再执行 mex(S) 运算的结果,即:SG(x) = mex({SG(y1), SG(y2), …, SG(yk)})
特别的,整个有向图游戏 G 的 SG 函数值被定义为有向图游戏起点 s 的 SG 函数值,即:SG(G) = SG(s)。
集合 - Nim 游戏
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40
| #include <iostream> #include <unordered_set> #include <cstring> using namespace std;
const int N = 110, M = 10010; int n, m; int s[N], f[M];
int sg(int x) { if(f[x] !=-1 ) return f[x]; unordered_set<int> S; for(int i=0;i<m;i++) { int sum = s[i]; if(x>=sum) S.insert(sg(x-sum)); } for(int i=0; ;i++) { if(!S.count(i)) { return f[x] = i; } } }
int main() { cin >> m; for(int i=0;i<m;i++) { cin >> s[i]; } cin >> n; memset(f, -1, sizeof f); int res = 0; for(int i=0;i<n;i++) { int x; cin >> x; res ^= sg(x); } if(res) puts("Yes"); else puts("No"); return 0; }
|