历史记录

清除记录

猜你想搜

AcWing热点
App
登录/注册

算法基础课——数学知识（四）笔记

作者：

jaylenwanghitsz , 2022-02-28 09:22:43 , 所有人可见 , 阅读 219

1

1

容斥原理 & 博弈论

容斥原理

第六章集合代数---1、2次课.png

$$|S_{1}\bigcup S_{2}\bigcup S_{3}\bigcup …\bigcup S_{m}|=\sum_{i=1}^{m}|S_{i}|-\sum_{1\leq i<j\leq m}^{m}|S_{i}\bigcap S_{j}|+\sum_{1\leq i<j<k\leq m}^{m}|S_{i}\bigcap S_{j}\bigcap S_{k}|-…+(-1)^{m-1}(S_{1}\bigcap S_{2}\bigcap …\bigcap S_{m})$$

证明：设 $x$ 被 $k$ 个集合共有，则在上述算式中 $x$ 被统计的次数：$$total=C_{k}^{1}-C_{k}^{2}+C_{k}^{3}-…+(-1)^{k-1}C_{k}^{k}$$ 对于一个二项式 $(1+x)^{n}$ ,展开得 $$(1+x)^{n}=C_{n}^{0}x^{0}+C_{n}^{1}x^{1}+…+C_{n}^{n}x^{n}$$ 当 $x=-1$ 时，原式-> $$C_{n}^{0}-C_{n}^{1}+C_{n}^{2}-…+(-1)^{n}C_{n}^{n}=0$$ 所以 $$C_{n}^{0}+C_{n}^{2}+…=C_{n}^{1}+C_{n}^{3}+…$$ 所以 $x$ 被统计得次数 $$total=C_{k}^{0}=1$$

题目：AcWing 890. 能被整除的数

容斥原理一共有 $2^{n}-1$ 项，枚举其中的每一项：for(int i = 1;i < (1 << n);i ++) 然后把 i 看成二进制数，从第 $1$ 到第 $n$ 位，每一位上的 01 表示这一位代表的集合是否被挑中。由此可以遍历所有的选法
这里常用的技巧就是利用数的二进制表示所蕴含的信息

时间复杂度：$O(2^{n}\times n)$

$$\sum_{i=0}^{n}C_{n}^{i}=2^{n}$$ 从 $n$ 个数中选取任意多个数的方案数总和是 $2^{n}$

计算每一项求 $\prod _{i=1}^{k}p_{i}$ 时间复杂度是 $O(k)$

代码

AcWing 892. 台阶-Nim游戏

代码

博弈论

NIM游戏 —— 模板题 AcWing 891. Nim游戏

给定 $N$ 堆物品，第 $i$ 堆物品有 $A_{i}$ 个。两名玩家轮流行动，每次可以任选一堆，取走任意多个物品，可把一堆取光，但不能不取。取走最后一件物品者获胜。两人都采取最优策略，问先手是否必胜。

我们把这种游戏称为 $NIM$ 博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。
所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。
$NIM$ 博弈不存在平局，只有先手必胜和先手必败两种情况。

定理： $NIM$ 博弈先手必胜，当且仅当 `A1 ^ A2 ^ … ^ An != 0`

证明：
- 当先手面临 0 ^ 0 ^ 0 ^...^ 0 = 0 时，先手必输
- 当先手面临 A1 ^ A2 ^ … ^ An == x != 0 时，假设 $x$ 的最高位 $1$ 来自于 $A_{i}$ ，则从 $A_{i}$ 中拿走 Ai - Ai ^ x ,这样原式-> A1 ^ A2 ^ ...^Ai ^ x ^ A(i+1) ^ ... ^ An == x ^ x == 0 .
  - 如此，每次后手都要面临异或值为 $0$ 的状态
  - 接下来证明后手每次都会使异或值非0
    - 假设后手变化了 Ai ，而异或值仍为 $0$ ，则
      - A1 ^ A2 ^ ... ^ Ai ^ … ^ An == 0
      - A1 ^ A2 ^ ... ^ Ai' ^ … ^ An == 0
    - 把两个等式异或起来，得
      - Ai ^ Ai' == 0 -> Ai == Ai'
    - 因此后手不可能在做出操作的情况下仍使结果为 $0$
  - 这样，每次先手都可以把异或值变成 $0$ ，最终后手要面临无法操作的局面而失败
代码

公平组合游戏 $ICG$

若一个游戏满足：

1.由两名玩家交替行动；
2.在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
3.不能行动的玩家判负；
则称该游戏为一个公平组合游戏。
$NIM$ 博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。
任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

$Mex$ 运算

设 $S$ 表示一个非负整数集合。定义 $mex(S)$ 为求出不属于集合 $S$ 的最小非负整数的运算，即：
$mex(S) = min{x}$, $x$ 属于自然数，且 $x$ 不属于 $S$

$SG$ 函数

在有向图游戏中，对于每个节点 $x$ ，设从 $x$ 出发共有 $k$ 条有向边，分别到达节点 $y_1, y_2, …, y_k$ ，定义 $SG(x)$ 为 $x$ 的后继节点 $y_1, y_2, …, y_k$ 的 $SG$ 函数值构成的集合再执行 $mex(S)$ 运算的结果，即：
$$SG(x) = mex({SG(y_1), SG(y_2), …, SG(y_k)})$$
特别地，整个有向图游戏 $G$ 的 $SG$ 函数值被定义为有向图游戏起点 $s$ 的 $SG$ 函数值，即 $$SG(G) = SG(s)$$。

对应于现实的 $NIM$ 游戏，每个节点可以看作是一个局面，相邻的节点意味着一个局面可以通过合法操作到达下一个局面

计算 $SG$ 函数，需要先定义 $SG(终点)=0$ ，一点值为 $0$ 表示无法行动，就是必败的局面

有向图游戏的和 —— 模板题 AcWing 893. 集合-Nim游戏

设 $G_1, G_2, …, G_m$ 是 $m$ 个有向图游戏。定义有向图游戏 $G$，它的行动规则是任选某个有向图游戏 $G_i$，并在 $G_i$ 上行动一步。$G$ 被称为有向图游戏 $G_1, G_2, …, G_m$ 的和。
有向图游戏的和的 $SG$ 函数值等于它包含的各个子游戏 $SG$ 函数值的异或和，即：

SG(G) = SG(G1) ^ SG(G2) ^ … ^ SG(Gm)

定理

有向图游戏的某个局面必胜，当且仅当该局面对应节点的SG函数值大于 $0$。
有向图游戏的某个局面必败，当且仅当该局面对应节点的SG函数值等于 $0$。
- 因为终点状态定义为 $0$ ，如果一个点能到 $0$ ，那这个点的值一定大于 $0$, 这个点必胜；如果一个点值等于 $0$ ，则它一定不能到 $0$ ,这个点必败
如果当前局面对应节点的值为 $k$ ，则该节点一定可以走到 $0$ ~ $k-1$ 中的任意一个节点对应的局面
代码