2020-09-02发表2021-01-22更新OI笔记11 分钟读完 (大约1714个字)

博弈论学习笔记

Alice 和 Bob 又开始玩游戏了……

SG 函数

对于博弈论中的局面 $S$，定义它的 SG 函数为 $SG(S)=\text{mex} SG(T)$，其中 $T$ 是 $S$ 的后继局面。
对于无法做出任何移动的局面（先手必败态），我们称之为 P 态，否则称之为 N 态（先手必胜态）。

SG 定理：一个局面 $S$ 是 P 态当且仅当 $SG(S)=0$

这个定理也可以这样理解：可以到达 P 态的局面是 N 态，所有移动都导致 N 态的局面是 P 态。
另一个非常有用的结论：对于由多个局面 $S_1, S_2,…S_n$ 组成的博弈游戏，该局面的 SG 函数是所有 $SG(S_i)$ 的异或和。

经典 Nim

有 $n$ 堆石子，每堆石子有 $a_i$ 个，每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取，最后没石子可取的人就输了。问是否存在先手必胜的策略。
$n\le 10^7, a_i\le 10^9$

根据 SG 定理，容易发现 $SG(S_i)=a_i$，故先手必胜当且仅当 $a_i$ 的异或和不为0。

阶梯 Nim

有 $n$ 堆石子，每堆石子有 $a_i$ 个，每人每次可从任意一堆石子里取出任意多枚石子移动到前面一堆石子，可以取完，不能不取，最后无法移动的人就输了（此时所有石子都在位置0）。问是否存在先手必胜的策略。
$n\le 10^7, a_i\le 10^9$

若先手移动偶数堆的石子到奇数堆去，那么后手可以立刻将其移入下一个偶数堆，这样看起来对奇数堆毫无影响。但是如果先手移动奇数堆的石子去偶数堆，则可能会将其移入第 0 堆。因此，只有在奇数堆移动石子是本质的。

“从奇数堆移动一些石子去偶数堆”等价于从奇数堆拿走一些石子扔掉，因子对奇数堆做 Nim 即可。

一道栗题

有 $n$ 个箱子，每个箱子有 $a_i$ 个石头，一开始所有箱子都是关着的。
Alice 和 Bob 轮流操作，每次可以至少打开一个被关闭的箱子，或者选择一个已经开着的箱子拿走里面至少一个石头。
不能操作的输，求先手必胜还是后手必胜。
$1\le n\le 10^5, 0\le a_i\le 10^9$

考虑如果存在一个 $a_1,a_2,…a_n$ 的子集使其异或和为 0，先手选择一个极大的这样的子集打开，则丢给后手了一个 P 态；此时后手一定要考虑去开新的箱子，但是不存在新的子集使其异或和为 0 了，因此后手并不能挽回局面，故此时为 N 态。
如果不存在呢？那么无论先手怎么开箱子，得到的都一定是 N 态，故此时为 P 态。

因此结论：先手必胜当且仅当存在一个子集使之异或和为 0。
大力枚举 $O(2^n)$ ，可通过线性基降成 $O(n)$ 。

又一道栗题

有 $n$ 堆石子，每堆石子有 $a_i$ 个，每人每次可从任意一堆石子里取出一枚石子扔掉，但任意两次不能取同堆的石子。最后无法移动的人输，问是否存在先手必胜的策略。
$n\le 10^7, a_i\le 10^9$

若存在一堆石子，满足其中石子的个数比其它堆石子个数总和还多，则先手是必胜的，即一直取这一堆就好了。
如果不存在呢？那么任意时刻，不能存在一堆石子，使得其中石子的个数多于其它堆石子个数总和。这意味着所有石子都要被取走，因此直接判断奇偶性即可，复杂度 $O(n)$。

双一道栗题

给你 $n$ 张卡片，每张卡片的两个面各有数字 $a_i$ 和 $b_i$，每个面都有 $1/2$ 的概率出现为卡片的正面，卡牌正反面的概率相互独立，求把所有卡牌正面数字拿来玩 Nim 游戏，先手必胜的概率。
$n\le 5\times 10^5, a_i,b_i\le 10^{18}$

设 $S=\bigoplus\limits_{i=1}^na_i$，定义序列 $c_i=a_i\oplus b_i$，则问题等价于求序列 $c$ 有多少个子集使得异或和为 $S$，线性基维护即可，复杂度 $O(n\log a_i)$。

代码：

class LB {
  public: LL a[101];
    void ins(LL x){
        for(int i = 63; i + 1; i--){
            if(!(x & (1ll << i))) continue; 
            if(a[i]) x ^= a[i];
            else{
                for(int j = i - 1; j + 1; j--) if(x & (1ll << j)) x ^= a[j];
                for(int j = i + 1; j <= 63; j++) if(a[j] & (1ll << i)) a[j] ^= x;
                a[i] = x; break;
            }
        }
    }
    int sz() {int cnt = 0; for(int i = 0; i <= 63; i++) if(a[i]) cnt++; return cnt;}
    bool ext(LL x) {for(int i = 63; i + 1; i--) if(x & (1ll << i)) x ^= a[i]; return x == 0 ? 1 : 0;}
} D;

LL n, sum, a[CN], b[CN];
n = read(); for(int i = 1; i <= n; i++) a[i] = read(), b[i] = read(), D.ins(a[i] ^ b[i]), sum ^= a[i];

if(!D.ext(sum)) puts("1/1");
else{
    int k = D.sz();
    LL ans = 1; while(k--) ans <<= 1;
    printf("%lld/%lld", ans - 1, ans);
}

叒一道栗题

有 $n$ 堆石子（$n$ 是偶数），每堆石子有 $a_i$ 个，每人每次可从任意 $n/2$ 堆石子里取出至少一枚石子扔掉。最后无法移动（有石子的堆的数量 $\le n/2$）的人输，问是否存在先手必胜的策略。
$n\le 10^7, a_i\le 10^9$

考虑若存在石子个数为 1 的堆，设堆数为 $x(x>0)$，则有情况如下：

$x > n/2$，则先手必败，因为无法避免在操作中形成空堆；
$x\le n/2$，则先手必胜，因为先手只要令操作后 $x>n/2$ 即可

剩下的唯一问题是不存在石子个数为 1 的堆的情况。
可以考虑放宽限制，即考虑石子个数为 2 的堆的情况。容易发现石子个数为 2 的情况依然可以归结到上述的两种讨论，因此直接猜出结论：先手必胜当且仅当石子个数最小的堆的数量 $\le n / 2$。