【x义x】超实数和不平等博弈
x义x
·
·
个人记录
这种一堆数学推导的东西写了有啥意义……就当自己的笔记吧
1.超实数基础知识
首先定义超实数 surreal number 是什么东西。
一个超实数 x 由两个超实数集合 x_L,x_R 构成，记作 \{x_L|x_R\}。
但是 x_L 和 x_R 要满足一个条件：任意 x_R 里的元素都不 \le 任何 x_L 里的元素。（但是我们以后会破坏这条规定……）
超实数由两个超实数集构成，禁止套娃
但是什么是 \le？于是定义超实数集上的偏序关系 \le。
称 x\le y 当且仅当
\forall d\in x_L,d\not\ge y
且
\forall d\in y_R,d\not\le x
这个 \le 满足自反性：
下面使用（类似）数学归纳法（的东西）证明。
首先 x=\{|\}（这个记号表示 x_L=x_R=\varnothing）的时候原命题显然成立（直接代入 \le 的定义）。
下面证明：
\forall d\in x_L,d\not\ge x
\forall d\in x_R,d\not\le x
对于 \forall d\in x_L，如果 d\le d，那么 x\le d 显然不成立（在 x_L 中选取 d 自身），得到第一个柿子；
对于 \forall d\in x_R，如果 d\le d，那么 d\le x 显然不成立（在 x_R 中选取 d 自身），得到第二个柿子。
因为这两个柿子成立，所以原命题显然成立（直接代入 \le 的定义）。
这个 \le 具有传递性：
- 如果 x\le y,y\le z，则 x\le z。
思路还是（类似）数学归纳法（的东西）。
首先对于 x=y=z=\{|\} 原命题显然成立。
如果 \forall d\in x_L,y\le z,z\le d 可以推出 y\le d，那么必然有 d\not\ge z，否则可推出 y\le d 与事实矛盾。同理可推出 \forall d\in z_R,d\not\le x。
其实还应该满足反对称性：
接下来你会看到如果 = 代表常规的，x_L=y_L 且 x_R=y_R 的那种 =，反对称性会不满足。
所以事实上我们是拿这个定义新的 = 的……
也就是说，两个 不同的 元素 x,y，可能使得 x\le y,y\le x同时满足。很快你会看到一个例子。
据说可以证明 x\le y 和 y\le x 中至少有一个成立，博主不会证。而且这个结论意义不大，因为如果引入 *,\uparrow,\downarrow 后这个结论显然不成立，而很多游戏都存在先手必胜局面。
聊了这么多，让我们真正地见识一些超现实数。
$\{0|\}$ 称作 $1$。显然有 $0\le 1$，$0\not\ge 1$。
$\{|0\}$ 称作 $-1$。显然有 $0\ge -1$，$0\not\le -1$。
再进一步：
$\{1|\}$ 称作 $2$。对称地，$\{|-1\}$ 称作 $-2$。
$\{0|1\}$ 称作 $\frac 1 2$。很快你会知道这是为什么。（标记 $\color{red}2$）对称地 $\{-1|0\}$ 称作 $-\frac 1 2$。
容易（？）发现有：
$$-2\not\ge -1\not\ge-\tfrac 1 2\not\ge 0\not\ge \tfrac 1 2\not\ge 1\not\ge 2$$
$$-2\le -1\le-\tfrac 1 2\le 0\le \tfrac 1 2\le 1\le 2$$
提一句：对于 $\{-1|1\}$ 这种我们就不讲了，原因是它等于 $0$。
通过这种方式我们能构建实数到超实数的对应关系，称为 **达利函数**：
$$\delta(x)=\begin{cases}\{|\}&(x=0)\\\{\delta(x-1)|\}&(x>0,x\in Z)\\\{|\delta(x+1)\}&(x<0,x\in Z)\\\{\delta(\frac{j-1}{2^k})|\delta(\frac{j+1}{2^k})\}&(x=\frac j{2^k},j,k\in Z)\end{cases}$$
无法表示为 $\frac j{2^k}$ 的实数就靠逼近。
注意，一个超实数不一定有对应的实数。
接下来定义**加法运算** $+$。
$$(x+y)_L=\{\{d+y,d\in x_L\}\cup\{x+d,d\in y_L\}\}$$
$$(x+y)_R=\{\{d+y,d\in x_R\}\cup\{x+d,d\in y_R\}\}$$
（此处需要证明 $x+y$ 仍是一个超实数，即超实数在加法上封闭。~~我不会证，所以~~略。）
显然这个加法运算的单位元是 $0$。这也是我们把它称作 $0$ 的原因。$\large\color{red}^{1}
一个非 0 超实数 x 的加法逆元是 \{-d,d\in x_R|-d,d\in x_L\}，0 的加法逆元是 0。
再举个具体的加法算数栗子。
\tfrac 1 2+\tfrac 1 2=\{\tfrac 1 2|\{\tfrac 1 2,1|2\}\}
可以证明，\{\frac 1 2,1|2\}=\frac 3 2，\{\frac 1 2|\frac 3 2\}=1，即 \frac 1 2+\frac 1 2=1。这也是我们把它称作 \frac 1 2 的原因。\large\color{red}^{2}
容易（？）发现这个加法满足交换律，结合律。
还有一组结论：
a\le b,c\le d\rightarrow a+c\le b+d
a\ge b,a+b\le c+d\rightarrow c\le d
总结一下，这种加法在某些方面和实数上的加法具有相同的性质。（事实上还有 \delta(x)+\delta(y)=\delta(x+y),x,y\in R）
2.超实数和不平等博弈
再来讲讲不平等博弈。为了方便把不平等博弈的一个状态描述称为一个棋局。我们称两个玩家为 Alice 和 Bob，当然，先手者可能是 Alice 也可能是 Bob。
举个简单的栗子：改造版 nim 游戏。有好几叠积木，每块积木上写着 A 或 B。Alice 可以进行的操作是，选择一块尚未被移除的写着 A 的积木，移除它和它顶上的所有积木；Bob 相反，可以选定写着 B 的积木。
我们使用两个棋局集合描述一个棋局。（是不是很熟悉？）A 集合是如果当前 Alice 先手，他走一步后可能转移到的所有棋局；B 集合相反。
显然，如果 AB 集合中有一个为空，那么他先手时就显然会无路可走，失败。后手时？不好说。
接下来我们干脆就用一个超实数描述一个棋局。
首先来回顾超实数的加法。一个棋局可能有很多子游戏，玩家操作时可以任选一个子游戏操作。非常显然，超实数的加法就对应两个游戏的合并。
加法逆元就对应一个棋局的反棋局：Alice 和 Bob 的“操作权限”互换。即 Alice 改成选定 B 积木，Bob 改成选定 A 积木。
$0$ 棋局显然是一个先手必败的棋局。
任何一个棋局的反棋局与它自身同时进行，也是先手必败，后手的最佳策略就是：在另一半棋局复制对手上一步的行动。
事实上 $x\not\le 0,x\ge 0$ 就代表 $x$ 是一个 Alice 必胜的棋局， $x\not\ge 0,x\le 0$ 就代表 $x$ 是一个 Bob 必胜的棋局，$x=0$ 表示后手必胜，$x\not\le 0,x\not\ge 0$ 表示先手必胜。
好的，回来分析改造版 nim 游戏，先考虑只有一叠积木的情况。
空的积木塔：显然是 $0$。
一块写着 A 的积木：$\{0|\}=1$。
以此类推，$N$ 块写着 A 的积木：$\delta(N)$。
相反，$N$ 块写着 B 的积木： $\delta(-N)$。
算了直接丢个结论图吧：
多个子游戏直接实数加法即可。
## 3.超超实数？？？
~~这个“超超”的前缀总是让我想到[超形上学部](http://scp-wiki-cn.wikidot.com/component:pataphysics-theme)~~
~~找不到超形上学部中心页，只好丢了个版式页进来~~
注意超实数要求右集合的任何一个元素都不小于等于左集合的任意一个元素，然而不符合这个要求的游戏是非常常见的。
比如在刚才的游戏中加入一种同时写着 A 和 B 的积木，显然，单独一块这种积木的游戏对应的“超实数”应该是：
$$\{0|0\}$$
把它记作 $*$。
$*$ 是一个先手必胜的棋局，同时有 $*+*=0$。
$*$ 小于（不大于）任何一个正数，大于任何一个负数，但是和 $0$ 无法比较： $*\not\le 0,*\not\ge 0$。
再考虑 $\uparrow=\{0|*\},\downarrow=\{*|0\}$。$\uparrow$ 描述了这样一个棋局：Alice 先手则 Bob 无路可走，Alice 胜；Bob 先手则转为 $*$ 局面且 Alice 先手，还是 Alice 胜，是一个 Alice 必胜局面。$\downarrow$ 反之。$\uparrow=-\downarrow$。
但是 $\uparrow$ 小于任何一个正数。你可以把它认为是无穷小一类的东西。
注意 $*+\uparrow$ 是先手必胜的，但是 $*+\uparrow+\uparrow$ 又变成 Alice 必胜了。
如何在考虑 $*,\uparrow,\downarrow$ 的情况下判断整个游戏是先手必胜、后手必胜？丢结论：
好力，接下来看例题。
## 4.例题
### [P4225](https://www.luogu.com.cn/problem/P4225)
~~可以从题目名称里体会到出题人溢出屏幕的求生欲。~~
总共只有 $23$ 种情况，于是手推可以得出每一种棋局对应的超实数。这题只有 $0,\pm 1,\pm \tfrac 1 2$ 和 $*,\uparrow,\downarrow$。
显然只要 $*$ 的游戏的个数不为 0，随机 kill 完 $*$ 游戏的个数是偶数/奇数的概率都是 $\frac 1 2$。
用上一点生成函数的知识应该容易计算 $\sum\uparrow$ 的部分。即计算 $(x+1)^n(x^{-1}+1)^m=x^{-m}(x+1)^{n+m}$ 中 $x^i(i<0)$ 的系数和。很好做。
用上较多的生成函数的知识容易计算 $\sum \texttt{数字}$ 的部分。即计算 $(x+1)^a(x^{-1}+1)^c(x^2+1)^b(x^{-2}+1)^d=x^{-c-d}(x+1)^{a+c}(x^2+1)^{b+d}$ 中 $x^i(i<0)$ 的系数和。
枚举 $(x^2+1)^{b+d}$ 中展开出的 $Cx^i$ 项，容易发现可以和它配对对答案产生贡献的 $(x+1)^{a+c}$ 中展开出的 $Cx^j$ 项要满足 $j<-i$，于是把 $x^j$ 的系数做一个前缀和即可。
总的来说是道只要懂了不平等博弈就没有难点的题目。
### [HDU3544](http://acm.hdu.edu.cn/showproblem.php?pid=3544)
此题问题在于每次操作都会把游戏分成两个游戏相加。
$1\times 1$ 的巧克力：$0$。
$1\times 2$ 的巧克力：$1$。
以此类推，$1\times N$ 的巧克力：$\delta(N-1)$。
$2\times 1$ 的巧克力：$-1$。
$2\times 2$ 的巧克力：$\{-2|2\}=0
2\times 3$ 的巧克力：$\{-1|4\}=0
2\times 4$ 的巧克力：$\{-1,0|6\}=1
以此类推，2\times N 的巧克力：\delta(-1+\frac N 2)
打个究极大表可以发现
M\times N,2^k\le M<2^{k+1}$ 的巧克力：$\delta(-M+2+\frac {N-2}{2^k})