容斥原理+简单博弈论

标签：石子 台阶 游戏 int 博弈论 容斥 bigoplus 原理 SG

容斥原理

2个韦恩图的面积并:\(S_1+S_2-S_1S_2\)

3个韦恩圆的面积并:\(S_1+S_2+S_3-S_1S_2-S_1S_3-S_2S_3+S_1S_2S_3\)

n个韦恩圆的面积并:\(S_1+S_2+...+S_n-S_1S_2-...-S_{n-1}S_n+...+(-1)^{n-1}S_1S_2...S_n\)

共有\(C_n^1+C_n^2+...+C_n^n=2^n-1\)项 \(O(2^n)\)

从集合的角度来看:

\[|S_1\bigcup S_2\bigcup...\bigcup S_n|=\Sigma_i|S_i|-\Sigma_{ij}|S_i\bigcap S_j|+\Sigma_{ijk}|S_i\bigcap S_j\bigcap S_k|... \]

\[\because C_k^0-C_k^1+C_k^2-C_k^3+C_k^4+...+(-1)^{n}C_k^k=1\\ \therefore C_k^1-C_k^2+C_k^3-C_k^4+...+(-1)^{n-1}C_k^k=1\\ \]

给定一个整数 \(n\) 和 \(m\) 个不同的质数 \(p_1,p_2,…,p_m\)。

请你求出 \(1∼n\) 中能被 $p_1,p_2,…,p_m $中的至少一个数整除的整数有多少个。

1~10中能被2或3整除的数的个数：

\[S_2=\{2,4,6,8,10\}\\ S_3=\{3,6,9\}\\ S_2\bigcap S_3=\{6\}\\ |S_2\bigcup S_3|=|S_2|+|S_3|-|S_2\bigcap S_3|=5+3-1=7\\ \]

只需要计算\(2^m\)次

\[1-n中p的倍数的个数:\lfloor \frac{n}{p}\rfloor \\ |S_{p_1}\bigcup S_{p_2}\bigcup ... \bigcup S_{p_n}| = |S_{p_1}|+...+|S_{p_n}|-|S_{p_1}\bigcap S_{p_2}|-...+|S_{p_1}\bigcap S_{p_2} \bigcap S_{p_3}|+...\\ \]

那么如何用代码表示每个集合选与不选的状态呢？

一共有\(2^n-1\)中状态，由1开始

这里使用二进制，以\(m=4\)为例，\((1101)_2\)表示选中集合\(S_1,S_2,S_4\)，所以集合中的元素个数为\(\frac{n}{p_1p_2p_4}\)

再根据公式，可以得到前面的系数为\((-1)^{3-1}=1\)

所以在这个状态下就是\(res += n/ (p1*p1*p4)\)

但是需要特别注意枚举的质数的积大于n的情况，这里需要特判一下

以及为什么要 \(n/(p_1\times ... \times p_n)\)而不是\(n/p_1/.../p_n\)，是因为直接整除会有精度误差

#include <iostream>
#include <cmath>

using namespace std;

typedef long long ll;

const int N = 20;

int p[N];
int n, m;

int main()
{
    cin >> n >> m;
    for(int i = 0; i < m; i ++)    cin >> p[i];
    ll res = 0;
    for(int i = 1; i < pow(2, m); i ++)
    {
        int cnt = 0;
        ll t = 1;
        for(int j = 0; j < m; j ++)
        {
            if(i >> j & 1)
            {
                if(t * p[j] > n)
                {
                    t = -1;
                    break;
                }
                t *= p[j];
                cnt ++;
            }
        }
        if(t == -1) continue;
        // cout << cnt << " " << t << endl;
        if(cnt % 2) res += n / t;
        else    res -= n / t;
    }
    cout << res << endl;
    return 0;
}

博弈论

公平组合游戏ICG

若一个游戏满足：

1. 由两名玩家交替行动；

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

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

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

有向图游戏

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

先手必胜状态：先手进行某一个操作，留给后手是一个必败状态时，对于先手来说是一个必胜状态。即先手可以走到某一个必败状态。

先手必败状态：先手无论如何操作，留给后手都是一个必胜状态时，对于先手来说是一个必败状态。即先手走不到任何一个必败状态。

Mex运算

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

也就是集合里面不存在的最小的自然数，比如\(mex\{1,2,3\} = 0\)

SG函数

终点状态为全部是0，\(SG(终点)=0\)

在有向图游戏中，对于每个节点\(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(y1), SG(y2), …, SG(yk)})\( 特别地，整个有向图游戏\)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) \bigoplus SG(G_2) \bigoplus … \bigoplus SG(G_m)\)

定理模板

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

NIM游戏

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

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

定理： NIM博弈先手必胜，当且仅当 \(A_1 \bigoplus A_2 \bigoplus … \bigoplus A_n != 0\)

证明：

1. 操作到最后，每堆石子个数都是\(0\)的时候，\(0 \bigoplus 0 \bigoplus 0 ... \bigoplus 0 = 0\)，先手必败

2. \(A_1 \bigoplus A_2 \bigoplus … \bigoplus A_n = x \neq 0\)

   假设\(x\)的二进制表示中最高的一位1在第\(k\)位，那么\(A_1-A_n\)中必然存在一个数\(A_i\)，\(A_i\)的第\(k\)位二进制为1

   那么，存在\(A_i \bigoplus x < A_i\)，所以从第\(i\)堆中拿走 \(A_i - ( A_i \bigoplus x)\) 个石子是合法的

   那么第\(i\)堆就剩下 \(A_i - (A_i - ( A_i \bigoplus x)) = A_i \bigoplus x\)个石子

   \(A_1 \bigoplus A_2 \bigoplus ... \bigoplus A_n \bigoplus x = x \bigoplus x = 0\)

3. \(A_1 \bigoplus A_2 \bigoplus … \bigoplus A_n = 0\)

   要证明从\(A_1 - A_n\)中任选一堆拿任意个，可以使得 \(A_1 \bigoplus A_2 \bigoplus … \bigoplus A_n\) 的值不是0

   反证法：

   存在\((A_1 \bigoplus A_2 \bigoplus … \bigoplus A_i') \bigoplus (A_1 \bigoplus A_2 \bigoplus … \bigoplus A_i) = 0\)

   则有 \(A_i' \bigoplus A_i = 0 \Rightarrow A_i' = A_i\)

基于上述证明：

1. 如果先手面对的状态是\(A_1 \bigoplus A_2 \bigoplus … \bigoplus A_n \neq 0\)那么先手总可以通过拿走某一堆若干个石子，将局面变成\(A_1 \bigoplus A_2 \bigoplus … \bigoplus A_n = 0\) .如此重复，最后一定是后手面临最终没有石子可拿的状态。先手必胜。
2. 如果先手面对的局面是\(A_1 \bigoplus A_2 \bigoplus … \bigoplus A_n = 0\)，那么无论先手怎么拿，都会将局面变成\(A_1 \bigoplus A_2 \bigoplus … \bigoplus A_n \neq 0\)，那么后手总可以通过拿走某一堆若干个石子，将局面变成\(A_1 \bigoplus A_2 \bigoplus … \bigoplus A_n = 0\)。如此重复，最后一定是先手面临最终没有石子可拿的状态。先手必败。

台阶-NIM游戏

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

e.g. 石子数量为2 1 3

先手将3台阶的1块拿到2台阶，变为 2 2 2

然后对手从偶数k台阶拿多少到奇数k-1台阶，就从奇数k-1台阶拿多少到偶数k-2台阶，假如对手从3台阶拿多少到2，就相应的从1拿多少到地上（0台阶）

此时，我们需要将奇数台阶看作是一个的经典Nim游戏，如果先手时奇数台阶上的值的异或值为0，则先手必败，反之必胜

先手时，如果奇数台阶异或非0，根据经典Nim游戏，先手总有一种方式使奇数台阶异或为0，于是先手留了奇数台阶异或为0的状态给后手，于是轮到后手：
①当后手移动偶数台阶上的石子时，先手只需将对手移动的石子继续移到下一个台阶，这样奇数台阶的石子相当于没变，于是留给后手的又是奇数台阶异或为0的状态
②当后手移动奇数台阶上的石子时，留给先手的奇数台阶异或非0，根据经典Nim游戏，先手总能找出一种方案使奇数台阶异或为0

因此无论后手如何移动，先手总能通过操作把奇数异或为0的情况留给后手，当奇数台阶全为0时，只留下偶数台阶上有石子。

（核心就是：先手总是把奇数台阶异或为0的状态留给对面，即总是将必败态交给对面）

因为偶数台阶上的石子要想移动到地面，必然需要经过偶数次移动，又因为奇数台阶全0的情况是留给后手的，因此先手总是可以将石子移动到地面，当将最后一个（堆）石子移动到地面时，后手无法操作，即后手失败。

因此如果先手时奇数台阶上的值的异或值为非0，则先手必胜，反之必败！

集合-NIM游戏

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

1. 我们可以确定对于确定的集合\(S\)，以及唯一确定的数字，其\(SG\)值也是唯一确定的

   即使在不同石子堆中，由于取石子的方式唯一，所以其终点和分支是唯一的，所以在所有石子堆中，在集合\(S\)确定的条件下，每个数的\(SG\)值都保持不变。

2. 假设取石子的集合为\(\{2,5\}\)，且仅有一堆石子，石子数为10

					->	3(1)	->	1(0)
		->	5(2)	->	0(0)          
10(1)				
    	->  8(0)   -> 	3(1)	->	1(0)
                
            		->  6(1)	->	1(0)
                    			->	4(0)	->	2(1)	->	0(0)

我们设终点的SG值为10，当仅有一堆石子的时候，如果\(SG(10) \neq 0\)必胜，否则必败。

当\(SG\)值不为0时，因为\(SG\)值经过了\(mex\)运算，所以其连接的点中必然有一点\(SG\)值为0，当走到\(SG\)为0的这一点时，由于\(mex\)运算，该点连接的所有点的值必然不为0。

又因为终点的\(SG\)值为0，所以只要先手的\(SG\)值不为0，就可以一直走到\(SG\)值为0的点，从而最终走向终点。

3. 当有任意多堆石子的时候

假设任意每堆石子的\(SG\)值已知

10(3)
15(5)
20(2)

每堆石子的\(SG\)值都是与其连接的点的\(SG\)值中，最小的且与连接点的值不同的最小非负整数，所以选择时都可以选择\(SG\)值\(0-SG(x)\)之间的任意数

e.g.

\[\because SG(10)=3\\ \therefore SG(10)可以选择连接点的SG值是[0,3)的范围 \]

那么，将每堆石子的\(SG\)值取出来，可以发现这些值拼接起来就可以称为NIM游戏

当\(SG(x_1)\bigoplus SG(x_2) \bigoplus SG(x_3) = m\neq 0\)时，可以选择\(SG\)值最大的那一个，如\(SG(x_2)\)，使得

\[SG(x_2')=SG(x_2) \bigoplus m\\ \Rightarrow SG(x_1)\bigoplus SG(x_2')\bigoplus SG(x_3) = SG(x_1)\bigoplus SG(x_2)\bigoplus SG(x_3) \bigoplus m = m \bigoplus m=0 \]

所以，当所有石子堆的异或值不等于0的时候必胜

我们可以通过类似于递归+记忆化搜索的方式实现\(SG\)函数

#include <iostream>
#include <set>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 110, M = 10010;
int minn = 10010;

int s[N], sgv[M];
int k, n, res = 0;

int sg(int x)
{
    if(sgv[x] != -1)    return sgv[x];
    if(x < minn)    return sgv[x] = 0;
    set<int> st;
    for(int i = 0; i < k; i ++)
    {
        if(x >= s[i])    st.insert(sg(x-s[i]));
    }
    for(int i = 0; ; i ++)
    {
        if(!st.count(i))    return sgv[x] = i;
    }
}

int main()
{
    scanf("%d", &k);
    for(int i = 0; i < k; i ++) scanf("%d", &s[i]), minn = min(minn, s[i]);
    scanf("%d", &n);
    memset(sgv, -1, sizeof(sgv));
    while(n --)
    {
        int x;
        scanf("%d", &x);
        res ^= sg(x);
    }
    if(res) printf("Yes\n");
    else    printf("No\n");
    return 0;
}

拆分-NIM游戏

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

相比于集合-Nim，这里的每一堆可以变成小于原来那堆的任意大小的两堆

即\(a[i]\)可以拆分成\((b[i],b[j])\),为了避免重复规定\(b[i]>=b[j]\),即：\(a[i]>b[i]>=b[j]\)

相当于一个局面拆分成了两个局面，由\(SG\)函数理论，多个独立局面的\(SG\)值，等于这些局面\(SG\)值的异或和。
因此需要存储的状态就是\(sg(b[i])^sg(b[j])\)（与集合-Nim的唯一区别）

因为这题中原堆拆分成的两个较小堆小于原堆即可，因此任意一个较小堆的拆分情况会被完全包含在较大堆中，因此\(set\)可以开全局。

#include <iostream>
#include <cstring>
#include <set>

using namespace std;

const int N = 110;
int s[N];

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

int main()
{
    memset(s, -1, sizeof(s));
    
    int n, res = 0;
    cin >> n;
    while(n --)
    {
        int x;
        cin >> x;
        res ^= sg(x);
    }
    if(res) cout << "Yes" << endl;
    else    cout << "No" << endl;
    return 0;
}

标签：石子,台阶,游戏,int,博弈论,容斥,bigoplus,原理,SG
From： https://www.cnblogs.com/xushengxiang/p/17013502.html