算法基础（13）

容斥原理

回顾中学学过的韦恩图（Venn diagram）：

将三个集合推广到n个集合，设 U 中元素有 n 种不同的属性，而第 i 种属性称为$P_i$ ，拥有属性$P_i$的元素构成集合$S_i$ 那么：

$$\begin{align*} \left| \bigcup\limits_{i=1}^n S_i\right|=& \sum\limits_{i=1}\left| S_i\right|-\sum\limits_{i<j}\left| S_i \cap S_j\right| + \sum\limits_{i<j<k}\left| S_i \cap S_j \cap S_k\right|-\dots\\ &+(-1)^{m-1}\sum\limits_{a_i<a_{i+1}}\left| \bigcap\limits^m_{i=1} S_{a_i}\right|+\dots+(-1)^{n-1}\left| S_i \cap \dots \cap S_n\right|\\ \\ =& \sum\limits^n_{m=1}(-1)^{m-1}\sum\limits_{a_i<a_{i+1}}\left| \bigcap\limits^m_{i=1} S_{a_i}\right| \end{align*}$$

关于容斥原理的相关知识可以参考：OI Wiki-容斥原理

简单证明一下：设$x$在$k$个集合中出现过，则$x$在上式中被计算的次数：

$$cnt=C_k^1-C_k^2+C_k^3+\dots +(-1)^{k-1}C_k^k$$

又因为：

$$C_k^0(-1)^k+C_k^1(-1)^{k-1}+C_k^2(-1)^{k-2}+\dots +C_k^k=-1+cnt=(1-1)^k=0$$

所以$x$在上式中共被计算了一次。

性质：上式有多少项：

$$C_n^1+C_n^2+C_n^3+\dots +C_n^n$$

补一项$C_n^0$，则有：

$$C_n^0+C_n^1+C_n^2+C_n^3+\dots +C_n^n=(1+1)^n=2^n$$

因此上式中一共有$2^n-1$项。

例题：能被整除的数（Acwing 890）

给定一个整数$n$和$m$个不同的质数$p_1,p_2,…,p_m$。请你求出1~n中能被$p_1,p_2,…,p_m$中的至少一个数整除的整数有多少个。

数据范围：$1 \le m \le 16, 1\le n,p_i \le 10^9$

暴力做法的时间复杂度是$O(mn)$，一定会超时，考虑用容斥原理做，时间复杂度为$O(2^m)$，$2^{16}=65536<10^7$（每秒大约能算$10^7 \sim 10^8$），以n = 10, m=2, 3为例，集合$S_2$表示能被2整数的数的集合，题目是要求两个集合的并集的元素个数。

$|S_p|$如何求：$|S_p|$表示$1 \sim n$中$p$的倍数的个数，即$\lfloor \frac{n}{p} \rfloor$；$|S_{p_1} \cap S_{p_2}\dots\cap S_{p_k}|$如何求：因为$p_1, p_2, \dots, p_k$是互质的数，所以$|S_{p_1} \cap S_{p_2}\dots\cap S_{p_k}|$就是$1 \sim n$中$p_1p_2\dots p_k$的公倍数的个数，即$\lfloor \frac{n}{p_1p_2 \dots p_k} \rfloor$，计算这一项的时间复杂度就是$O(k)$，则算法总的时间复杂度就是$O(2^m\cdot k)=O(2^m \cdot m)=O(2^{16} \cdot 16)=O(2^{20})=10^6$。

Tips：枚举$2^n-1$种选法时可以采用位运算的方式，从$1 \sim 2^{n}-1$枚举i，把i看成n位的二进制数，每一位对应一个集合，是1就表示这个集合被选了，是0就表示这一个集合没有被选，因此就可以用二进制数来枚举所有选法了 。确认二进制数的每一位上的数是不是1，就可以用i >> k & 1。

#include<iostream>
using namespace std;

typedef long long LL;
const int N = 20;

int n, m;
int p[N];

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 ++)   //1 << m 表示2的m次方
    {
        int t = 1, cnt = 0;   //t 表示当前几个质数的乘积，cnt表示当前选法中几个集合
        for(int j = 0; j < m; j ++)
            if(i >> j & 1)    //若当前位是1，表示该位对应的集合有被选中
            {
                cnt ++;
                if((LL) t * p[j] > n)   //若质数的乘积大于n了，就直接跳出
                {
                    t = -1;
                    break;
                }
                t *= p[j];
            }
        if(t != -1)
        {
            if(cnt % 2)  res += n / t;  //若选中集合个数为奇数，就加上n / t
            else  res -= n / t;         //若是偶数就减去
        }
    }
    
    cout << res << endl;
    
    return 0;
}

简单博弈论

首先来看一些相关的定义：

可参考：OI Wiki-博弈论

公平组合游戏ICG：若一个游戏满足：

1. 由两名玩家交替行动

2. 在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关；

3. 不能行动的玩家判负；

则称该游戏为一个公平组合游戏。

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

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

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

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

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

先手必胜状态与先手必败状态：

• 先手必胜状态：拿完之后，剩下的状态是必败状态，即可以把当前的状态变成先手必败状态；

• 先手必败状态：拿完之后，剩下的所有状态都是先手必胜状态。

定理： NIM博弈先手必胜，当且仅当$a_1 \oplus a_2 \oplus \dots\oplus a_n \ne 0$ （$\oplus$表示异或）

简单证明一下：

1. 若当前不能进行任何操作，即每堆中物品都是0，$0\oplus 0 \oplus \dots\oplus 0 = 0$；

2. 若当前异或值不是0，$a_1 \oplus a_2 \oplus \dots\oplus a_n =x\ne 0$，则一定能通过一次操作从某一堆里拿走若干个物品，让剩下的异或值变成0，证明：

设$x$的二进制表示中最高的一位1在第$k$位，则在$a_1 \sim a_n$中必然存在一个数$a_i$，$a_i$的第$k$位是1，则有：

$$a_i \oplus x < a_i$$

那么我们可以从$a_i$这一堆中拿走$a_i-(a_i \oplus x)$，即把$a_i$变成了$(a_i \oplus x)$，那现在所有数的异或值就变为：

$$a_1 \oplus a_2 \oplus \dots\oplus a_i \oplus x \dots \oplus a_n =x \oplus x=0$$

即证明了若当前异或值不为0，则可以通过一次操作使得剩下的数的异或值为0。

1. 若当前的异或值是0，即$a_1 \oplus a_2 \oplus \dots\oplus a_n \ne 0$ ，进行任何一次操作后，剩下的数的异或值不会是0，证明：

反证法，若对$a_i$这个堆拿走一些物品后，剩下的个数为$a_i’$，剩下的数的异或值为0，则有：

$$a_1 \oplus a_2 \oplus \dots\oplus a_i‘ \dots \oplus a_n =0$$

把上式和原式合起来取异或，则有$a_i \oplus a_i’=0$，即$a_i=a_i’$，然而操作必须是要拿走若干物品，不能不拿，即必有$a_i’<a_i$，因此就矛盾，假设错误，即证。

可见，如果最开始各堆$a_i$的异或值不是0，先手状态的异或值一定不是0，后手的状态异或值一定是0，则先手必胜；否则若最开始各堆$a_i$的异或值是0， 则先手必败。

例题1：NIm游戏（Acwing 891）

给定$n$堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。

数据范围：$1 \le n \le10^5$，$1 \le$每堆石子数$\le 10^9$

#include<cstdio>

int main()
{
    int n;
    scanf("%d", &n);
 
    int res = 0;   
    while(n--)
    {
        int x;
        scanf("%d", &x);
        res ^= x;
    }
    
    if(res)  puts("Yes");   //若最开始各堆a_i的异或值不是0，则先手必胜
    else puts("No");
    
    return 0;
}

例题2：台阶-Nim游戏（Acwing 892）

现在，有一个n级台阶的楼梯，每级台阶上都有若干个石子，其中第$i$级台阶上有$a_i$个石子($i≥1$)。两位玩家轮流操作，每次操作可以从任意一级台阶上拿若干个石子放到下一级台阶中（不能不拿）。已经拿到地面上的石子不能再拿，最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。

数据范围：$1≤n≤10^5, 1≤a_i≤10^9$。

考虑一个样例，共三级台阶，每级的石子个数是2，1， 3，则先手有必胜策略。我们先手从第3级拿下1个到第2级，让第1级和第3级的石子都保持一致，都是2个；然后根据对手的操作，我们始终让1，3级台阶的石子个数一致：若对手从第3级往下拿几个，我们就从第一级往下拿几个；若对手从第1级往下拿几个，我们就从第三级往下拿几个；若对手从第2级往下拿几个，我们就从第1级往下拿几个。这样对手看的1,3级台阶石子个数永远是1致的，我看的到永远是不一致的，则对手会先遇到0,0的情况，即我是必胜的。

推广到一般的情况：我们只需要关注奇数级台阶上石子的个数，若其异或值$a_1 \oplus a_3 \oplus \dots\oplus a_n \ne 0$ ，则先手必胜；若为0则先手必败。

#include<iostream>
using namespace std;

int main()
{
    int n;
    int res = 0;
    
    scanf("%d", &n);
    
    for(int i = 1; i <= n; i ++)
    {
        int x;
        scanf("%d", &x);
        if(i % 2)   //只取奇数台阶，求异或值
            res ^= x;
    }
    
    if(res) puts("Yes");
    else puts("No");
    
    return 0;
}

例题3：集合-Nim游戏（Acwing 983）

给定$n$堆石子以及一个由$k$个不同正整数构成的数字集合$S$。现在有两位玩家轮流操作，每次操作可以从任意一堆石子中拿取石子，每次拿取的石子数量必须包含于集合$S$，最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。

数据范围：$1≤n,k≤100,1≤s_i,h_i≤10000$

解这道题前先了解几个概念：

Mex运算：设$S$表示一个非负整数集合。定义mex(S)为求出不属于集合$S$的最小非负整数的运算，即：mex(S) = min{x}，$x$属于自然数（从0开始），且$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)。

有向图游戏的和：设$G_1, G_2, …, G_m$ 是$m$个有向图游戏。定义有向图游戏$G$，它的行动规则是任选某个有向图游戏$G_i$，并在$G_i$上行动一步。$G$被称为有向图游戏$G_1, G_2, …, G_m$的和。

有向图游戏的和的SG函数值等于它包含的各个子游戏SG函数值的异或和，即：

$$SG(G) = SG(G_1) \oplus SG(G_2) \oplus ... \oplus SG(G_m)$$

定理：

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

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

上面定理证明的思路和第一个Nim游戏是一样的，用$SG(x_i)$代替$a_i$即可。

通过SG函数，把n个图的局面通过异或的方式判断出必胜或必败的局面，把指数级的状态（n维）变成1维状态。

（以下图为例，设每次可取的石子数为2，5，共三堆石子，每堆中个数分别为10，7， 5。则求解过程是，把每一堆当作一个有向图游戏，求出每堆的SG值，最后再取异或值$SG(10) \oplus SG(7) \oplus SG(5)$，若结果不为0，则先手必胜，否则先手必败。）

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

using namespace std;

const int N = 110, M = 10010;  

int n, m;
int s[N], SG[M];   //s[]表示每堆中石子的个数，SG[]表示有向图的SG[]值

int sg(int x)    //用记忆化搜索来求有向图的SG值
{
    if(SG[x] != -1)  return SG[x];   //如果当前局面已经计算过了，就不需要重复计算
    
    unordered_set<int> S;   //用哈希表来存当前可以达到的局面
    for(int i = 0; i < n; i ++)    //枚举可取的石头数
        if(x >= s[i])  S.insert(sg(x - s[i]));
    
    for(int i = 0; ; i ++)    //求当前点的SG值
        if(!S.count(i))
            return SG[x] = i;
}

int main()
{
    cin >> n;   //可以取的石子的方案数
    for(int i = 0; i < n; i ++)  cin >> s[i];
    cin >> m;   //石子的堆数
    
    memset(SG, -1, sizeof SG);
    
    int res = 0;
    
    for(int i = 0; i < m; i ++)   //每一堆石子看成一个有向图游戏，最后求出所有堆SG的异或值
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }
    
    if(res)  puts("Yes");
    else  puts("No");
    
    return 0;
}

例题4：拆分—Nim游戏

给定n堆石子，两位玩家轮流操作，每次操作可以取走其中的一堆石子，然后放入两堆规模更小的石子（新堆规模可以为0，且两个新堆的石子总数可以大于取走的那堆石子数），最后无法进行操作的人视为失败。问如果两人都采用最优策略，先手是否必胜。

数据范围：$1≤n,a_i≤100$

拆分—Nim游戏可以用$SG$函数来做，求出每堆石子的$SG$值，最后再求异或。对于每一个局面$a_i$，假设它可以变成局面$(b_1, b_2)$，则它们的$SG$值的关系为$SG(b_1, b_2)=SG(b_1) \oplus SG(b_2)$。

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

using namespace std;

const int N = 110;

int n, 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;
}