容斥原理:
韦恩图求n个集合全集
|A_1 ∪ A_2 ∪ … ∪ A_n| = |A_1| + |A_2| + … + |A_n| - |A_1 ∩ A_2| - |A_1 ∩ A_3| - … - |A_{n-1} ∩ A_n| + |A_1 ∩ A_2 ∩ A_3| + |A_1 ∩ A_2 ∩ A_4| + … + (-1)^(n+1) |A_1 ∩ A_2 ∩ … ∩ A_n|
1个圆加起来 - 2个圆加起来 + 三个圆加起来 + …
时间复杂度(即加减加减过程的总项数): O(2 ^ n) (二项式定理)
容斥原理过程中,项数即从n个数里挑k个数的和,也就是从n个数里挑任意多个数的方案数,每个数选或不选两种情况因此cn1 + cn2 + ... = 2 ^ n - cn0(1);
https://www.acwing.com/problem/content/892/
Sk = {k, 2k, 3k, ...} (pk < n)
算若干S集合并集:容斥原理
如何求[1, n]中Sp的个数
[Sp] = [n / p];
[Sk U Sm] = [n / (k * m)] (题目p都为质数,因此能同时整除的只有他们的公倍数)
由上知暴力求解每个集合的个数时间复杂度无法满足
那么如何实现容斥原理公式?
1. dfs:
参考
1. https://www.acwing.com/solution/content/7873/
2. https://www.acwing.com/solution/content/146855/
2. 位运算:枚举所有集合时用
已知:1)从n个集合中选k个集合情况已全部包含在容斥原理中 2)奇数符号为正,偶数为负
实现思路:
用位运算枚举所有选取情况i∈[1, 2^n -1]: i看成二进制数, n个数故有n位;
i的二进制表示中每位看作每个集合是否被选;
每种选择方式对应一种选法,枚举2^n - 1次穷举所有选法
tip: 判断某数二进制k位上是否为1: i >> k & 1
代码:
https://www.acwing.com/activity/content/code/content/6459239/
博弈论:
关键词: Nim游戏 Nim游戏定理 ICG公平组合游戏 (chatgpt一下告诉你基本概念)
补充:Nim游戏属于公平组合游戏,棋类游戏除外(垃圾chatgpt不对)
Nim游戏定理证明:
https://www.acwing.com/file_system/file/content/whole/index/content/4810/:01:11:43 - 01:24: 14
只要异或和不为0,意味着先手操作完留给对手的异或和总是为0;而对方将自己手里异或和为0的情况操作一下总会给我提供一种异或和不为0的操作方式,因此先手实在是赢得太多了,麻了都
异或原因: 关键词:kNim游戏
SG函数 SG函数公式
SG(EndNode) = 0;
一步之内:
Therefore, 只有一个图则SG(x) != 0, x必胜;SG(x) == 0;
(终点为0状态所以非0状态一定有方式走到0, 0的状态一定走不到0)
多图:
必输:任何一个图都走不了
SG(StartofX1Map) ^ SG(StartofX2Map) ^ ... != 0必胜
证明和Nim游戏证明类似
记忆化搜索:递归过程被算过的不再重复计算,将指数级时间复杂度计算压缩
吹水:
leetcode关注空间复杂度,重语法
算法竞赛只关注时间复杂度