四、容斥原理

假设有三个圆如图重叠，使用$S_i$表示三个圆的面积，那么整个图的面积为 S =   S 1 + S 2 + S 3 − S 1 ∩ S 2 − S 1 ∩ S 3 − S 2 ∩ S 3 + S 1 ∩ S 2 ∩ S 3

S= ​S1​+S2​+S3​−S1​∩S2​−S1​∩S3​−S2​∩S3​+S1​∩S2​∩S3​​同理，对于四个圆相互重叠后，整个图形的面积为 S =   S 1 + S 2 + S 3 + S 4 − S 1 ∩ S 2 − S 1 ∩ S 3 − S 1 ∩ S 4 − S 2 ∩ S 3 − S 2 ∩ S 4 − S 3 ∩ S 4 + S 1 ∩ S 2 ∩ S 3 + S 1 ∩ S 3 ∩ S 4 + S 2 ∩ S 3 ∩ S 4 − S 1 ∩ S 2 ∩ S 3 ∩ S 4

S= S1+S2+S3+S4−S1∩S2−S1∩S3−S1∩S4−S2∩S3−S2∩S4−S3∩S4+S1∩S2∩S3+S1∩S3∩S4+S2∩S3∩S4−S1∩S2∩S3∩S4$$\begin{array}{rl}S=& S_1+S_2+S_3+S_4\\ & -S_1\cap S_2-S_1\cap S_3-S_1\cap S_4-S_2\cap S_3-S_2\cap S_4-S_3\cap S_4\\ & +S_1\cap S_2\cap S_3+S_1\cap S_3\cap S_4+S_2\cap S_3\cap S_4\\ & -S_1\cap S_2\cap S_3\cap S_4\end{array}$$

S= ​S1​+S2​+S3​+S4​−S1​∩S2​−S1​∩S3​−S1​∩S4​−S2​∩S3​−S2​∩S4​−S3​∩S4​+S1​∩S2​∩S3​+S1​∩S3​∩S4​+S2​∩S3​∩S4​−S1​∩S2​∩S3​∩S4​​

讨论：式子中元素个数

假设有$n$个数，那么总共有$${\mathrm{C}}_n^0+{\mathrm{C}}_n^1+{\mathrm{C}}_n^2+{\mathrm{C}}_n^3+...+{\mathrm{C}}_n^n=2^n$$其中等式左边表示从$n$个数中选择任意多个数的方案数，等式右边等于$2^n$是因为对于每个数而言只有选或者不选择两种情况，$n$个数总共有$2^n$。所以对于式子中元素个数为$${\mathrm{C}}_n^1+{\mathrm{C}}_n^2+{\mathrm{C}}_n^3+...+{\mathrm{C}}_n^n=2^n-{\mathrm{C}}_n^0=2^n-1$$所以容斥原理时间复杂度为$2^n$。

讨论：式子中为什么是“+-+-”不断重叠的

假设有式子$$|S_i\cup S_2\cup ...\cup S_n|=\sum _i|S_i|-\sum _{i,j}|S_i\cap S_j|+\sum _{i,j,k}|S_i\cap S_j\cap S_k|-...$$其中，$|S|$操作表示集合中$S$的个数。

假设有元素$x$出现在了$k\in [1,n]$个集合中，根据上述等式右边，可以得出元素$x$总共被计算了$${\mathrm{C}}_k^1-{\mathrm{C}}_k^2+{\mathrm{C}}_k^3-{\mathrm{C}}_k^4+..+(-1{)}^{k-1}{\mathrm{C}}_k^k=1$$所以可以知道对于等式左边中的任意一个元素$x$，在统计的时候只会被统计一次，所以容斥原理的等式是正确的。

容斥原理公式的代码实现原理：二进制枚举
S =   S 1 + S 2 + S 3 + S 4 − S 1 ∩ S 2 − S 1 ∩ S 3 − S 1 ∩ S 4 − S 2 ∩ S 3 − S 2 ∩ S 4 − S 3 ∩ S 4 + S 1 ∩ S 2 ∩ S 3 + S 1 ∩ S 3 ∩ S 4 + S 2 ∩ S 3 ∩ S 4 − S 1 ∩ S 2 ∩ S 3 ∩ S 4

S= ​S1​+S2​+S3​+S4​−S1​∩S2​−S1​∩S3​−S1​∩S4​−S2​∩S3​−S2​∩S4​−S3​∩S4​+S1​∩S2​∩S3​+S1​∩S3​∩S4​+S2​∩S3​∩S4​−S1​∩S2​∩S3​∩S4​​总共有$2^n-1$项，每一项前面的符号取决于所选集合的个数。如果集合个数为奇数，则为$+$，否则为$-$。

对于每个集合的枚举，使用位运算依次枚举$1...2^n-1$，即有$n$位二进制数，表示$n$个集合。如果某位上值为$1$表示选择该集合，$0$表示不选择该集合。

4.1 能被整除的数

ACwing 890

如果采用暴力枚举每个数，那么时间复杂度是$O(nm)$，显然会超时，所以使用容斥原理。对于样例，建立两个数组 S 2 = [ 2 , 3 , 6 , 8 , 10 ] S 3 = [ 3 , 6 , 9 ]

​S2​=[2,3,6,8,10]S3​=[3,6,9]​分别表示能被$2、3$整除的数，题目要求$|S_2\cup S_3|$，根据容斥原理有： ∣ S 2 ∪ S 3 ∣ =   ∣ S 2 ∣ + ∣ S 3 ∣ − ∣ S 2 ∩ S 3 ∣ =   5 + 3 − 1 =   7

= = = |S2∪S3||S2|+|S3|−|S2∩S3|5+3−17$$\begin{array}{rl}& |S_2\cup S_3|\\ =& |S_2|+|S_3|-|S_2\cap S_3|\\ =& 5+3-1\\ =& 7\end{array}$$

= = = ​∣S2​∪S3​∣∣S2​∣+∣S3​∣−∣S2​∩S3​∣5+3−17​时间复杂度为$O(2^m)$

其中对于$|S_p|$，即$1...n$中$p$的倍数的个数，有$$|S_p|=\lfloor \frac{n}{p}\rfloor$$对于$|S_{p_1}\cap S_{p_2}\cap S_{p_3}\cap ...\cap S_{p_k}|$，有$$|S_{p_1}\cap S_{p_2}\cap S_{p_3}\cap ...\cap S_{p_k}|=\lfloor \frac{n}{p_1{p}_2...P_k}\rfloor$$对于每个集合计算时间复杂度为$O(k)$，所以整个算法时间复杂度为$O(m{2}^m)$。

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

const int N = 20;

int p[N];

int main() {
    int n, m; 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, s = 0; // t表示所有质数乘积 s表示当前二进制数中1的个数
        for (int j = 0; j < m; j++)
            if (i >> j & 1) {
                if ((LL) t * p[j] > n) {
                    t = -1;
                    break;
                }
                t *= p[j];
                s++;
            }

        if (t != -1) {
            if (s % 2) res += n / t;
            else res -= n / t;
        }
    }
    cout << res << endl;
    return 0;
}
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

五、博弈论

NIM博弈

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

我们把这种游戏称为NIM博弈。把游戏过程中面临的状态称为局面。整局游戏第一个行动的称为先手，第二个行动的称为后手。若在某一局面下无论采取何种行动，都会输掉游戏，则称该局面必败。

所谓采取最优策略是指，若在某一局面下存在某种行动，使得行动后对面面临必败局面，则优先采取该行动。同时，这样的局面被称为必胜。我们讨论的博弈问题一般都只考虑理想情况，即两人均无失误，都采取最优策略行动时游戏的结果。

NIM博弈不存在平局，只有先手必胜和先手必败两种情况。

定理

NIM博弈，若先手必胜，当且仅当 $$A_{1}xor{A}_{2}xor\dots xor{A}_n\ne 0$$反之，若先手必败，当且仅当 $$A_{1}xor{A}_{2}xor\dots xor{A}_n=0$$

定理证明：

• 当$A_1=A_2=...=A_n=0$时，有$A_{1}xor{A}_{2}xor...xor{A}_n=0$，显然先手必败；
• 当$A_{1}xor{A}_{2}xor...xor{A}_n=x\ne 0$时，先手一定可以通过若干操作使其异或值变成$0$。假设$x$二进制表示中最高的一位$1$在第$k$位，表示$A_1,A_2,...,A_n$中必存在一个数$A_i$的第$k$位二进制位为$1$，就会有$A_{i}xorx<A_i$。所以可以从第$i$堆石子中拿走$A_i-(A_{i}xorx)$个石子，于是第$i$的石子数目变成$$A_i-(A_i-(A_{i}xorx))=A_{i}xorx$$于是就有 A 1   x o r   A 2   x o r   …   x o r   A i   x o r   x   x o r   A i + 1 . . .   x o r   A n = x   x o r   x = 0
  A1 xor A2 xor … xor Ai xor x xor Ai+1... xor An=x xor x=0$$\begin{array}{rl}& A_{1}xor{A}_{2}xor\dots xor{A}_{i}xorxxor{A}_{i+1}...xor{A}_n\\ & =xxorx\\ & =0\end{array}$$
  ​A1​ xor A2​ xor … xor Ai​ xor x xor Ai+1​... xor An​=x xor x=0​所以对于先手而言，一定可以存在某种操作，使得剩余的石子的异或值为$0$。
• 当$A_{1}xor{A}_{2}xor...xor{A}_n=0$时，不管如何操作，剩余石子的异或值都一定不是$0$。反证法：假设从第$i$堆中拿走若干石子后，其值变成$A_i^{{}^{\prime }}$剩余石子异或值为$0$，则有 A 1   x o r   A 2   x o r   . . .   x o r   A n = 0 A 1   x o r   A 2   x o r   …   x o r   A i ′   x o r   A i + 1 . . .   x o r   A n = 0
  A1 xor A2 xor ... xor An=0A1 xor A2 xor … xor A′i xor Ai+1... xor An=0$$\begin{array}{rl}& A_{1}xor{A}_{2}xor...xor{A}_n=0\\ & A_{1}xor{A}_{2}xor\dots xor{A}_i^{{}^{\prime }}xor{A}_{i+1}...xor{A}_n=0\end{array}$$
  ​A1​ xor A2​ xor ... xor An​=0A1​ xor A2​ xor … xor Ai′​ xor Ai+1​... xor An​=0​将上面两个式子左右异或可得$$A_{i}xor{A}_i^{{}^{\prime }}=0$$因为$A_i^{{}^{\prime }}<A_I$，因此上式矛盾，所以有当$A_{1}xor{A}_{2}xor...xor{A}_n=0$时，不管如何操作，剩余石子的异或值都一定不是$0$。

所以根据上面三个性质可以知道：

• 如果先手开始操作的时候石子异或值不为$0$，那么先手一定可以通过操作将其变成$0$给后手。后手不管怎么操作，它操作后的石子的异或值一定不等于$0$。同理，先手又可以通过操作使其异或值变成$0$，后手又无论如何怎么操作石子，都会使其异或值变成$0$给先手…等于说先手开始操作石子的时候，石子的异或值一定不是$0$，后手开始操作的时候，石子的异或值一定是$0$，由于石子一定有被拿完的那一刻即游戏结束，所以先手必胜，后手必败。
• 如果先手开始操作的时候石子异或值是$0$，先手操作后一定不是$0$，后手操作后一定是$0$，…，一样的推导下去，到最后游戏结束的时候，先手必败，后手必胜。

公平组合游戏ICG

若一个游戏被称为公平组合游戏，应该满足：

• 由两名玩家交替行动；
• 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；
• 不能行动的玩家判负；

NIM博弈属于公平组合游戏，但城建的棋类游戏，比如围棋，就不是公平组合游戏。因为围棋交战双方分别只能落黑子和白子，胜负判定也比较复杂，不满足条件2和条件3。

有向图游戏

给定一个有向无环图，图中有一个唯一的起点，在起点上放有一枚棋子。两名玩家交替地把这枚棋子沿有向边进行移动，每次可以移动一步，无法移动者判负。该游戏被称为有向图游戏。

任何一个公平组合游戏都可以转化为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面向沿着合法行动能够到达的下一个局面连有向边。

Mex运算

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

SG函数

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

有向图游戏的和

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

定理

• 有向图游戏的某个局面必胜，当且仅当该局面对应节点的$SG$函数值大于$0$。
• 有向图游戏的某个局面必败，当且仅当该局面对应节点的$SG$函数值等于$0$。

定理说明：当只有一个有向图的时候，有向图的终点是$0$。

• 如果某个局面$SG\ne 0$，即先手可以进行操作将异或值变成$0$，后面根NIM游戏的定理一样，先手永远是非$0$，后手永远是$0$。有图可以知道非$0$的局面一定可以到达$0$的结束局面，因此先手必胜，后手必败。
• 如果某个局面$SG=0$，先手永远是$0$，后手永远是非$0$，由图可知，一开始为$0$的状态，后面到不了其它非$0$状态，所以后面结束的状态一定是$0$，所以先手必败，后手必胜。

对于多个有向图，则可以将所有图起点的$SG$值异或起来。
定理的证明同NIM游戏定理的证明。

5.1 Nim游戏

ACwing 891

对于样例，有两堆石子，每堆分别有石子$2、3$个。在NIM游戏中，先手必胜。原因是：先手如果先拿掉第二堆中的一个石子，则两堆石子数量一样，变成$2、2$。后面的游戏中，对于先手而言，他只需要和后手拿的石子数量一样，这样就可以保证只要后手有石子拿，那么先手就有石子拿，并且拿完后两堆石子依然保持一样，所以可以推出来先手必胜。

如果使用NIM游戏的定理，则代码非常简单。

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n;
    scanf("%d", &n);
    int res = 0;
    while (n--) {
        int x;
        scanf("%d", &x);
        res ^= x;
    }
    if (res) puts("Yes");
    else puts("No");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

5.2 台阶-Nim游戏

ACwing 892

先给结论：如果对所有第$k$堆石子，其中$k$为奇数，有$a_1\cap a_3\cap ...\cap a_n=x\ne 0$，先手必胜，否则先手必败。

• 假设$x\ne 0$，由之前的结论可知，先手操作一定可以使$x=0$。
  • 此时，后手如果从偶数台阶$u_4$拿走石子放到下一级奇数台阶$u_3$，那么先手可以将其拿到台阶$u_3$的石子继续放到下一级偶数台阶$u_2$上，这样就可以保证奇数台阶上的石子数量是不变的。所以先手抛给后手永远是一个$a_1\cap a_3\cap ...\cap a_n=0$的情况，先手自己得到的永远是$a_1\cap a_3\cap ...\cap a_n\ne 0$的情况，所以先手必胜。
  • 反之，如果此时后手是从奇数台阶拿走石子，由之前的结论可知，这个时候$a_1\cap a_3\cap ...\cap a_n\ne 0$，然后先手可以通过某种操作使其$a_1\cap a_3\cap ...\cap a_n=0$。因此对于先手一定是$a_1\cap a_3\cap ...\cap a_n\ne 0$，后手一定是$a_1\cap a_3\cap ...\cap a_n=0$，所以先手必胜。
• 假设$x=0$，分析同上。

#include <iostream>
#include <algorithm>

using namespace std;

int main() {
    int n; scanf("%d", &n);
    int res = 0;
    for (int i = 1; i <= n; i++) {
        int x; scanf("%d", &x);
        if (i & 1) res ^= x; // 判别奇偶
    }
    if (res) puts("Yes");
    else puts("No");
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

5.3 集合-Nim游戏

ACwing 893

假设现在仅有一堆石子，其有石子$10$个，每次只能从中取$2$或$5$个石子，则可以建立有向图

对于图中每个点，可以求出$SG$值，如图所示

对于$n$堆石子，可以使用同样的方式建立有向图并求出每个点的$SG$值。然后对每个图中起点的$SG$值进行异或运算，运用定理判定结果。

#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 110, M = 10010; // N堆石子，每堆M个

int n, m;
int s[N], f[M]; // s每堆石子个数 f表示sg函数的值

int sg(int x) {
    if (f[x] != -1) return f[x]; // 如果被算过，直接返回，每个状态仅计算一次，最多计算M次
    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++) // 求出每个点的SG
        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;
}
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

5.4 拆分-Nim游戏

ACwing 894

首先，因为堆的规模是不断减小的，所以游戏最后一定可以结束。

所以对每一个堆，可以求出该堆的每一个局面$SG$函数，最终将所有起点的$SG$函数值进行异或运算即可。

对于每一个堆的$SG$函数，每一个局面可以分成若干个两堆(即每两堆为一组)，如下图。

对于$sg(b_1,b_2)$可以由下式得到$$sg(b_1,b_2)=sg(b_1)xorsg(b_2)$$

#include <cstring>
#include <iostream>
#include <algorithm>
#include <unordered_set>

using namespace std;

const int N = 110;

int n;
int f[N];

int sg(int x) {
    if (f[x] != -1) return f[x];
    unordered_set<int> S;
    for (int i = 0; i < x; i++)
        for (int j = 0; j <= i; j++)
            S.insert(sg(i) ^ sg(j));
    for (int i = 0;; i++)
        if (!S.count(i)) return f[x] = i;
}

int main() {
    cin >> n;
    memset(f, -1, sizeof f);
    int res = 0;
    while (n--) {
        int x; cin >> x;
        res ^= sg(x);
    }
    if (res) puts("Yes");
    else puts("No");
    return 0;
}
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