[いろはちゃんコンテスト Day4 J]もう、諦めない 并不是题解而是超现实数入门（2）

· · 题解

AT_iroha2019_day4_j もう、諦めない 题解

前言

不会，再放弃了呢。

啊啊啊 physics0523（物理好き）佬写的题目背景真的好！大家都去把いろはちゃんコンテスト（伊吕波酱比赛）Day4 的题目背景读一遍啊啊啊啊啊——

题目描述

现有 n 个长方形，每个长方形有参数 (a_i,b_i,h_i,w_i)，定义“横着”切一个参数为 (a,b,h,w) 的长方形为选取 h 的一个非 1 因子 d，让它变成 d 个参数为 (a,b,h/d,w) 的长方形，而“竖着”切一个 (a,b,h,w) 的长方形为选取 w 的一个非 1 因子 d，让它变成 d 个参数为 (a,b,h,w/d) 的长方形。先手每次可以横着切任何一个长方形或竖着切一个 a=1 的长方形，后手每次可以横着切一个 b=1 的长方形或竖着切任何一个长方形。不能操作的人输。

给定 q 次询问，每次询问给定 \ell,r，问只保留下标在 \ell 至 r 之间的长方形，作为先手的你，能否胜利呢……

简单分析

对于 a_i=b_i=1 的部分分，这是一个对称博弈（impartial game），可以通过 Sprague–Grundy 定理推导出每个游戏的 Grundy 数，进而判断谁必胜。

而对于整题来说，这则是一个非对称博弈（partizan game）。与对称博弈的 Grundy 数和 Sprague–Grundy 定理一般，尝试给每个状态赋予一个权值。于是我们尝试定义超现实数——

超现实数（surreal number）入门

定义 1. 一个数 x 被递归地定义为一对数的集合 (X_L,X_R)，满足对于任意 x_L\in X_L,x_R\in X_R 有 x_R\le x_L 不成立。

定义 2. 递归地定义一个数 x 为 (X_L,X_R) 小于等于另一个数 y 为 (Y_L,Y_R) 当且仅当对于任何 x_L\in X_L，有 x_L\ge y 不成立，且对于任何 y_R\in Y_R，有 x\ge y_R 不成立，记作 x\le y。

这很符合直觉。某种意义上，x_L 和 x_R 提供了足够确定 x 的信息，因此只需要看 x_L 和 x_R 是否符合我们期待的条件即可。

定义 3. 一个数 x 大于等于 y 当且仅当 y\le x，记作 x\ge y。

定义 4. 一个数 x 等于 y 当且仅当 x\le y 且 y\le x，记作 x=y。

等等？为什么不直接定义为 X_L=Y_L,X_R=Y_R？马上你就会知道——

定义 4. 一个数 x 小于 y 当且仅当 y\le x 不成立且 x\le y，记作 x<y。

定义 5. 一个数 x 大于 y 当且仅当 y<x，记作 x>y。

定义 6. 一个数 x 不小于等于 y 当且仅当 x\le y 不成立，记作 x\nleq y。

定义 7. 一个数 x 不大于等于 y 当且仅当 x\ge y 不成立，记作 x\ngeq y。

等等有什么区别吗？对于数确实没有，但是需要证明一下——而且对于更广义的游戏确实有区别了，这个之后再说。

定义 8. 一个数 x 不等于 y 当且仅当 x=y 不成立，记作 x\neq y。

定义 9. 记 0 为 (\varnothing,\varnothing)，1 为 (\{0\},\varnothing)，-1 为 (\varnothing,0)。

注：为和等于不是一个概念。

定理 1. 0=0,1=1,-1=-1,0<1,-1<0,-1<1。

证明 1. 依定义。

定理 2. 若数 x\le y,y\le z，则 x\le z。

证明 2. 考虑无穷递降法。设 x\le y,y\le z,x\nleq z，x,y,z 分别为 (X_L,X_R),(Y_L,Y_R),(Z_L,Z_R)，如果不成立，则要么 \exists x_L\in X_L,z\le x_L，要么 \exists z_R\in Z_R,z_R\le x，但是我们在第一种情况下有有 y\nleq x_L,y\le z,z\le x_L，第二种情况下有 z_R\nleq y,z_R\le x,x\le y，根据无穷递降法可知不存在这样的 x,y,z。

推论 2.1 若数 x\le y,y\ngeq z，则 x\ngeq z。

推论 2.2 若数 x\le y,y\ngeq z，则 x\ngeq z。

推论 2.3 若数 x\le y,y<z，则 x<z。

推论 2.4 若数 x<y,y\le z，则 x<z。

推论 2.5 若数 x=z,y=w，则 x\le y,x<y,x\ge y,x>y,x\nleq y,x\ngeq y,x=y,x\neq y 分别当且仅当 z\le w,z<w,z\ge w,z\nleq w,z\ngeq w,z=w,z\neq w。

为什么无穷递降法是成立的？因为数就是递归定义的。

定理 3. 对于数 x，有 x\le x。

证明 3. 考虑无穷递降法。设 x 为 (X_L,X_R)。若 x\nleq x，则要么 \exists x_L\in X_L,x_L\ge x，要么 \exists x_R\in X_R,x\ge x_R，在第一种情况下，因为 x_L\in X_L，故根据 \le 的定义，有 x_L\nleq x_L，在第二种情况下，同理有 x_R\nleq x_R。根据无穷递降法可知不存在这样的 x。

推论 3.1 对于数 x 为 (X_L,X_R) 和任意 x_L\in X_L，有 x_L\ngeq x，任意 x_R\in X_R 有 x\ngeq x_R。

推论 3.2 对于数 x，x=x。

定理 4. 对于数 x 为 (X_L,X_R)，有 \forall x_L\in X_L,x_L<x。

证明 4. 考虑无穷递降法。已经证明过 x_L\ngeq x，只需证 x_L\leq x。设 x_L 为 (X_{LL},X_{LR})。若不成立，则要么 \exists x_{LL}\in X_{LL},x_{LL}\ge x，要么 \exists x_{R}\in X_R,x_R\le x_L。后者根据数的定义被保证不可能，而若前者成立，有 x_{LL}\ge x，又因为 x\nleq x_L，有 x_{LL}\nleq x_L。根据无穷递降法可知不存在这样的 x。

定理 5. 对于数 x 为 (X_L,X_R)，有 \forall x_R\in X_R,x<X_R。

证明 5. 考虑无穷递降法。已经证明过 x_R\nleq x，只需证 x_R\geq x。设 x_R 为 (X_{RL},X_{RR})。若不成立，则要么 \exists x_{RR}\in X_{RR},x_{RR}\le x，要么 \exists x_{L}\in X_L,x_R\le x_L。后者根据数的定义被保证不可能，而若前者成立，有 x_{RR}\le x，又因为 x\ngeq x_R，有 x_{RR}\ngeq x_R。根据无穷递降法可知不存在这样的 x。

定理 6. 对于数 x,y，x\le y 或 y\le x。

证明 6. 若 x\nleq y，设 x,y 为 (X_L,X_R),(Y_L,Y_R)，则要么 \exists x_L\in X_L,x_L\ge y，要么 \exists y_R\in Y_R,x\ge y_R，前者说明 y\le x_L\le x，后者说明 y\le y_R\le x。

推论 6.1 对于数 x,y，x<y 当且仅当 x\ngeq y，x>y 当且仅当 x\nleq y。

定义 10. 设数 x,y 为 (X_L,X_R),(Y_L,Y_R)，定义 x+y 为 (\{x+y_L|y_L\in Y_L\}\cup\{x_L+y|x_L\in X_L\},\{x+y_R|y_R\in Y_R\}\cup\{x_R+y|x_R\in X_R\})。

很符合直觉的定义。既符合我们对“数”的想象，也符合我们对于“博弈”的想象。但是等等，怎么证明 x+y 一定是一个数？如果不证明是数，怎么利用数的性质？这就需要我们引入——

定义 11. 一个伪数（pseudo-number）/游戏（game） x 被递归地定义为一对伪数的集合 (X_L,X_R)。

定义 12. 递归地定义一个伪数 x 为 (X_L,X_R) 小于等于另一个伪数 y 为 (Y_L,Y_R) 当且仅当对于任何 x_L\in X_L，有 x_L\ge y 不成立，且对于任何 y_R\in Y_R，有 x\ge y_R 不成立，记作 x\le y。

定义 13. 一个伪数 x 大于等于 y 当且仅当 y\le x，记作 x\ge y。

定义 14. 一个伪数 x 等于 y 当且仅当 x\le y 且 y\le x，记作 x=y。

定义 15. 一个伪数 x 小于 y 当且仅当 y\le x 不成立且 x\le y，记作 x<y。

定义 16. 一个伪数 x 大于 y 当且仅当 y<x，记作 x>y。

定义 17. 一个伪数 x 不小于等于 y 当且仅当 x\le y 不成立，记作 x\nleq y。

定义 18. 一个伪数 x 不大于等于 y 当且仅当 x\ge y 不成立，记作 x\ngeq y。

定义 19. 一个伪数 x 不等于 y 当且仅当 x=y 不成立，记作 x\neq y。

定义 20. 一个伪数 x 与 y 无关系当且仅当 x\nleq y 且 y\nleq x，记作 x||y。

是的，伪数就有可能出现没有关系的情况了，比如——

定义 21. 记伪数 \ast 为 (\{0\},\{0\})。

定理 7. \ast || 0。

证明 7. 依定义。

那么伪数有哪些性质呢？实际上，刚才我们大多数证明都没有用到数的 \nexists x_L\in X_L,x_R\in X_R,x_L\ge x_R，因此这些定理可以直接照搬！

定理 8. 若伪数 x\le y,y\le z，则 x\le z。

证明 8. 考虑无穷递降法。设 x\le y,y\le z,x\nleq z，x,y,z 分别为 (X_L,X_R),(Y_L,Y_R),(Z_L,Z_R)，如果不成立，则要么 \exists x_L\in X_L,z\le x_L，要么 \exists z_R\in Z_R,z_R\le x，但是我们在第一种情况下有有 y\nleq x_L,y\le z,z\le x_L，第二种情况下有 z_R\nleq y,z_R\le x,x\le y，根据无穷递降法可知不存在这样的 x,y,z。

推论 8.1 若伪数 x\le y,y\ngeq z，则 x\ngeq z。

推论 8.2 若伪数 x\le y,y\ngeq z，则 x\ngeq z。

推论 8.3 若伪数 x\le y,y<z，则 x<z。

推论 8.4 若伪数 x<y,y\le z，则 x<z。

推论 8.5 若伪数 x=z,y=w，则 x\le y,x<y,x\ge y,x>y,x\nleq y,x\ngeq y,x=y,x\neq y 分别当且仅当 z\le w,z<w,z\ge w,z\nleq w,z\ngeq w,z=w,z\neq w。

定理 9. 对于伪数 x，有 x\le x。

证明 9. 考虑无穷递降法。设 x 为 (X_L,X_R)。若 x\nleq x，则要么 \exists x_L\in X_L,x_L\ge x，要么 \exists x_R\in X_R,x\ge x_R，在第一种情况下，因为 x_L\in X_L，故根据 \le 的定义，有 x_L\nleq x_L，在第二种情况下，同理有 x_R\nleq x_R。根据无穷递降法可知不存在这样的 x。

推论 9.1 对于伪数 x 为 (X_L,X_R) 和任意 x_L\in X_L，有 x_L\ngeq x，任意 x_R\in X_R 有 x\ngeq x_R。

推论 9.2 对于伪数 x，x=x。

准备好进入“加法”的世界了吗？

定理 10. 对于任意伪数 x，x+0 即为 x。

证明 10. 考虑归纳。依定义，设 x 为 (X_L,X_R)，则 x+0 就是 (\{x_L+0|x_L\in X_L\},\{x_R+0|x_R\in X_R\})，根据归纳假设，它就是 (X_L,X_R)，即 x。

这是一个关于为而不是相等的定理！以下两个也是。

定理 11. 对于任意伪数 x,y，x+y 即为 y+x。

证明 11. 考虑归纳。依定义，设 x 为 (X_L,X_R)，y 为 (Y_L,Y_R)，则 x+y 就是 (\{x+y_L|y_L\in Y_L\}\cup\{x_L+y|x_L\in X_L\},\{x+y_R|y_R\in Y_R\}\cup\{x_R+y|x_R\in X_R\})，y+x 就是 (\{y+x_L|x_L\in X_L\}\cup\{y_L+x|y_L\in Y_L\},\{y+x_R|x_R\in X_R\}\cup\{y_R+x|y_R\in Y_R\})。根据归纳假设，它们是一样的。

定理 12. 对于任意伪数 x,y,z，(x+y)+z 即为 x+(y+z)。

证明 12. 考虑归纳。依定义，设 x 为 (X_L,X_R)，y 为 (Y_L,Y_R)，z 为 (Z_L,Z_R)，则 x+y 就是 (\{x+y_L|y_L\in Y_L\}\cup\{x_L+y|x_L\in X_L\},\{x+y_R|y_R\in Y_R\}\cup\{x_R+y|x_R\in X_R\})，y+z 就是 (\{y+z_L|z_L\in Z_L\}\cup\{y_L+z|y_L\in Y_L\},\{y+z_R|z_R\in Z_R\}\cup\{y_R+z|y_R\in Y_R\})。因此，(x+y)+z 就是 (\{(x+y)+z_L|z_L\in Z_L\}\cup\{(x+y_L)+z|y_L\in Y_L\}\cup\{(x_L+y)+z|x_L\in X_L\},\{(x+y)+z_R|z_R\in Z_R\}\cup\{(x+y_R)+z|y_R\in Y_R\}\cup\{(x_R+y)+z|x_R\in X_R\})，而 x+(y+z) 就是 (\{x+(y+z_L)|z_L\in Z_L\}\cup\{x+(y_L+z)|y_L\in Y_L\}\cup\{x_L+(y+z)|x_L\in X_L\},\{x+(y+z_R)|z_R\in Z_R\}\cup\{x+(y_R+z)|y_R\in Y_R\}\cup\{x_R+(y+z)|x_R\in X_R\})。根据归纳假设，它们是一样的。

定理 13. 对于任意伪数 x,y,z，x\le y 当且仅当 x+z\le y+z。

证明 13. 考虑归纳。设 x,y,z 为 (X_L,X_R),(Y_L,Y_R),(Z_L,Z_R)。

充分性. 若 x+z\le y+z，则根据加法和 \le 的定义，不存在 x_L\in X_L,x_L+z\ge y+z，也不存在 y_R\in Y_R,x+z\ge y_R+z，根据归纳假设，这等价于不存在 x_L\in X_L,x_L\ge y，也不存在 y_R\in Y_R,x\ge y_R，换言之 x\le y。

必要性. 根据对于任意伪数 w 为 (W_L,W_R)，有 \forall w_L\in W_L,w_L\ngeq w，且 \forall w_R\in W_R,w\ngeq w_R，根据加法的定义，我们有 \forall x_L\in X_L,x_L+z\ngeq x+z，且 \forall z_L\in Z_L,x+z_L\ngeq x+z，且 \forall y_R\in Y_R,y+z\ngeq y_R+z，且 \forall z_R\in Z_R,y+z\ngeq y+z_R，又因为 x\le y，故 \forall x_L\in X_L,x_L+z\ngeq y+z，且 \forall z_L\in Z_L,x+z_L\ngeq y+z，且 \forall y_R\in Y_R,x+z\ngeq y_R+z，且 \forall z_R\in Z_R,x+z\ngeq y+z_R，换言之，x+z\le y+z。

推论 13.1 对于任意伪数 x,y,z，x=y 当且仅当 x+z=y+z。

推论 13.2 对于任意伪数 x,y,z，x<y 当且仅当 x+z<y+z。

推论 13.3 对于任意伪数 x,y,z,w，若 x\le y,z\le w，则 x+z\le y+w。

定理 14. 对于任意数 x,y，x+y 是数。

证明 14. 考虑归纳。设 x,y 为 (X_L,X_R),(Y_L,Y_R)，根据归纳假设，x+y，即为 (\{x+y_L|y_L\in Y_L\}\cup\{x_L+y|x_L\in X_L\},\{x+y_R|y_R\in Y_R\}\cup\{x_R+y|x_R\in X_R\})，这两个集合里面的元素都是数，因此只需证明前面一个集合里的所有数都小于后面一个集合里的数。而显然有 \forall x_L\in X_L,x_L+y<x+y，\forall y_L\in Y_L,x+y_L<x+y，\forall x_R\in X_R,x+y<x_R+y，\forall y_R\in Y_R,x+y<x+y_R，根据小于的传递性得证。

好的……说了这么多，有什么用呢？我们不是想要一个类似 Grundy 数的东西来着？怎么样把一个游戏化简呢？

定理 15.（化简定理） 设伪数 x 为 (X_L,X_R) 和数 y 为 (Y_L,Y_R) 满足对于任意 x_L\in X_L,x_L\ngeq y，且对于任意 x_R\in X_R,y\ngeq x_R，且不存在 y_L\in Y_L 或 y_R\in Y_R 满足相同的条件，则 x=y。

证明 15.

$x\le y$. 如果不成立，则因为 $\nexists x_L\in X_L,x_L\ge y$，所以 $\exists y_R\in Y_R,x\ge y_R$。但我们又有不等式链 $\forall x_L\in X_L,x_L\ngeq y<y_R$ 且 $\forall x_R\in X_R,y_R\le x\ngeq x_R$，因此 $y_R$ 满足条件。矛盾！故成立。 > 某种意义上，若 $x$ 是数，则 $x$ 就是它的两个集合之间**最简单**，或者说**最先被创造出来的数**。 **定理 16.** $(-1)+1$ 为 $(\{-1\},\{1\})$，它等于 $0$。 **证明 16.** 依化简定理可得。 **定理 17.** 设伪数 $x$ 为 $(X_L,X_R)$，且任取 $Y_L,Y_R$ 满足 $\forall y_L\in Y_L,y_L\ngeq x$ 且 $\forall y_R\in Y_R,x\ngeq y_R$，则 $z$ 为 $(X_L\cup Y_L,X_R\cup Y_R)$ 满足 $z=x$。 **证明 17.** $z\le x$。只需证不存在 $x_L\in X_L,x_L\ge x$，$y_L\in Y_L,y_L\ge x$ 或 $x_R\in X_R,z\ge x_R$。中间的不存在性已经给出，而前者和后者的不存在性由推论 9.1 保证。 $x\le z$。只需证不存在 $x_L\in X_L,x\ge z$，$x_R\in X_R,x_R\ge z$ 或 $y_R\in Y_R,y_R\ge z$。最后一者的不存在性已经给出，而前两者的不存在性由推论 9.1 保证。 **推论 17.1** 设伪数 $x$ 为 $(X_L,X_R)$。若 $X_L$ 存在最大元 $x_L$，则 $x=(\{x_L\},X_R)$。若 $X_R$ 存在最小元 $x_R$，则 $x=(X_L,\{x_R\})$。 **定义 22.** 定义 $M_\alpha$（其中 $\alpha$ 是传统的非负整数！）为所有数 $x$ 为 $(X_L,X_R)$，满足 $X_L\cup X_R\subseteq \bigcup\limits_{\beta<\alpha}M_\beta$。记 $O_\alpha=\bigcup\limits_{\beta<\alpha}M_\beta,N_\alpha=M_\alpha\backslash O_\alpha$。对于 $x\in N_\alpha$，称 $\alpha$ 为 $x$ 的**生日**。 **定理 18.** 若 $O_\alpha$ 是有限集，其元素从小到大为 $x_1,x_2,\cdots,x_n$，则 $N_a=\{(\varnothing,\{x_1\}),(\{x_1\},\{x_2\}),\cdots,(\{x_{n-1}\},\{x_n\}),(\{x_n\},\varnothing)\}$。特别地，$\alpha=0$ 时，有 $N_\alpha=\{0\}$。 **证明 18.** 根据推论 17.1，只需要考虑 $(\{x_i\},\{x_j\})(i<j)$，$(\varnothing,\{x_i\})$ 和 $(\{x_i\},\varnothing)$。显然这些都是数。（除非 $\alpha=0$ 时需要考虑 $\{\varnothing,\varnothing\}$） **必要性.** 如果以上考虑的 $(X_L,X_R)$ 并未在等式右侧列出，则显然存在一个 $x_k$ 满足 $\forall x_L\in X_L,x_L<x_k$ 且 $\forall x_R\in X_R,x_k<x_R$。那么根据化简定理，这个数等于生日最小的一个 $x_k$，并不出现在 $N_\alpha$ 中。 **充分性.** 对于 $(\varnothing,\{x_1\})$，它小于所有 $x_k$。对于 $(\{x_n\},\varnothing)$，它大于所有 $x_k$。对于 $(\{x_i\},\{x_{i+1}\})$，它大于所有 $x_k(k\le i)$ 且小于所有 $x_k(k>i)$。因此，等式右侧的所有数都不出现在 $O_\alpha$ 中，因此出现在 $N_\alpha$ 中。 **推论 18.1** $|N_\alpha|=2^\alpha$。 **定理 19.** 定理 18. 中，对于 $(\varnothing,\{x_1\})$，它等于 $x_1+(-1)$。对于 $(\{x_n\},\varnothing)$，它等于 $x_n+1$。 **证明 19.** 考虑对 $\alpha$ 归纳地逐项验证。设 $\alpha\ge1$。 $(\varnothing,\{x_1\})$. 因为 $x_1$ 是最小的，有 $x_1=(\varnothing,\{x'_1\})$。$x_1+(-1)=(\varnothing,\{x_1\}\cup\{x'_1+(-1)\})=(\varnothing,\{x_1\})$。 $(\{x_n\},\varnothing)$. 因为 $x_n$ 是最大的，有 $x_n=(\varnothing,\{x'_{n'}\})$。$x_n+1=(\varnothing,\{x_n\}\cup\{x'_{n'}+1\})=(\varnothing,\{x_n\})$。 **定义 23.** 定义 $\alpha_+=\max M_\alpha,\alpha_-=\min M_\alpha$。 **定义 24.** 对于传统的整数 $\alpha \in \Z$，定义 $f(\alpha)=\begin{cases}\alpha_+&\alpha\ge 0\\(-\alpha)_-&\alpha<0\end{cases}$。 **定理 20.** 对于任意整数 $\alpha,\beta\in \Z$，有 $f(\alpha)+f(\beta)=f(\alpha+\beta)$，且 $f(\alpha)\le f(\beta)$ 当且仅当 $\alpha\le \beta$。 **证明 20.** 考虑到 $n_+=1+1+\cdots+1$（$n$ 个）和 $n_-=(-1)+(-1)+\cdots+(-1)$（$n$ 个），以及 $-1<0<1,(-1)+1=0$ 即证。 **定理 21.** 对于一个 $x$ 为 $(X_L,X_R)$，设集合 $S=\{\forall x_L\in X_L,y>g(x_L)\land \forall x_R\in X_R,y<g(x_R)|y\in\mathbb Z\}$，若 $\exists y\in \Z,y\in S$，则定义 $g(x)$ 是绝对值最小的这样的 $y$。 对任意数 $x$，有 $f(g(x))=x$。 **证明 21.** 考虑到 $f(y)$ 的生日为 $|y|$，根据化简定理即证。 **推论 21.1** 对于任意数 $x,y$，若 $g(x),g(y)$ 存在，$g(x+y)=g(x)+g(y)$，$g(x)\le g(y)$ 当且仅当 $x\le y$。特别地，$x=y$，当且仅当 $g(x)=g(y)$。 > 换言之，这里确定了一个超现实数的整数值（如果有）。 **定理 22.** 对于伪数 $x$ 为 $(X_L,X_R)$，定义一个“游戏”：每次左玩家可以选择 $x_L\in X_L$ 让 $x\gets x_L$，右玩家可以选择 $x_R\in X_R$ 让 $x\gets X_R$，无法操作的人输。那么，左玩家取后手必胜当且仅当 $x\ge 0$，右玩家取后手必胜当且仅当 $x\le 0$。 **证明 22.** 考虑归纳。 **左玩家取后手必胜，若 $x\ge 0$**。这是因为，$\forall x_R\in X_R,x_R\nleq x\ge 0$，因此无论右玩家怎么取都有 $x_R\leq 0$ 不成立，根据归纳假设左玩家必胜。 **左玩家取后手必输，若 $x\ngeq 0$**。这是因为，根据定义，若 $x\ngeq 0$，因为 $0$ 左右集均为空，一定存在 $x_R\in X_R$，满足 $x_R\le 0$，右玩家取这个 $x_R$ 就能必胜。 **右玩家取后手必胜，若 $x\le 0$**。这是因为，$\forall x_L\in X_L,x_L\ngeq x\le 0$，因此无论左玩家怎么取都有 $x_L\geq 0$ 不成立，根据归纳假设右玩家必胜。 **右玩家取后手必输，若 $x\nleq 0$**。这是因为，根据定义，若 $x\nleq 0$，因为 $0$ 左右集均为空，一定存在 $x_L\in X_L$，满足 $x_L\ge 0$，左玩家取这个 $x_L$ 就能必胜。 **推论 22.1** 对于伪数 $x$ 为 $(X_L,X_R)$，定义一个游戏：每次左玩家可以选择 $x_L\in X_L$ 让 $x\gets x_L$，右玩家可以选择 $x_R\in X_R$ 让 $x\gets X_R$，无法操作的人输。那么， $x>0$ 当且仅当左玩家必胜；$x<0$ 当且仅当右玩家必胜；$x=0$ 当且仅当后手必胜；$x||0$ 当且仅当先手必胜。 **定义 25.** 定义超现实数（相等的看做同一个）的全体的一个**Dedekind 分割**为一对集合 $q=(Q_L,Q_R)$，满足 $\forall l\in Q_L,r\in Q_R,l<r$。 > 等等这本身是一个超现实数吗……好吧，实际上超现实数太多了，它们形成了一个**真类**（proper Class），而超现实数要求左右集合都是集合。不过反正 OI 题里也只需要关心生日有限的超现实数对吧…… **定义 26.** 对于 Dedekind 分割 $p=(P_L,P_R)$，$q=(Q_L,Q_R)$，定义 $p\le q$ 当且仅当 $P_L\subseteq Q_L$，$p\ge q,p<q,p>q$ 类似定义。对于数 $x$，记 $x<p$（$p>x$），若 $x\in P_L$，否则记 $x>p$（$p<x$）。 **定理 23.** Dedekind 分割上的 $\le$ 是一个全序，若分割 $p<q$ 则存在数 $x$ 满足 $p<x<q$。 **证明 23.** 显然。 **定义 27.** 对于一个伪数 $x$，定义其**左分割**为 $L(x)=(\{y|y\ngeq x\},\{y|y\geq x\})$，**右分割** $R(x)=(\{y|y\le x\},\{y|y\nleq x\})$。（显然它们都是分割。）若数 $y$ 满足 $L(x)=L(y)$ 或 $L(x)=R(y)$，称 $y$ 是 $x$ 的**左值**。若数 $y$ 满足 $R(x)=L(y)$ 或 $R(x)=R(y)$，称 $y$ 是 $x$ 的**右值**。 **定理 24.** 对于伪数 $x$ 为 $X_L,X_R$，设 $L=\sup\limits_{x_l\in X_L}R(x_L),R=\inf\limits_{x_R\in X_R}L(x_R)$，则： - 若 $L<R$，则 $x$ 等于最简单（即，生日最小，或者说，不存在 $y_L,y_R$ 也符合）的数 $y$，满足 $L<y<R$。此时，$L(x)=L(y),R(x)=R(y)$。 - 否则，$L(x)=L,R(x)=R$。 > 等等 $\sup$ 和 $\inf$ 是什么……？对于 OI 中的短游戏（short game），每次只有有限种可能，理解成 $\max$ 和 $\min$ 就好了。 **证明 24.** 先**考虑 $L<R$ 的情形**。这样最简单的 $y$ 为 $(Y_L,Y_R)$ 满足 $\forall y_L\in Y_L,y_L<L$，且 $\forall y_R\in Y_R,R<y_R$，且 $L<y<R$。 $x\le y$. 若不然，则要么 $\exists x_L\in X_L,x_L\ge y$，要么 $\exists y_R\in Y_R,x\ge y_R$。前者说明 $y<R(x_L)$，与 $L$ 的定义矛盾。后者加上 $\exists x_R\in X_R,L(x_R)<y_R$ 说明 $x\ge y_R\ge x_R$，与 $x\ngeq x_R$ 矛盾。 $x\ge y$. 若不然，则要么 $\exists x_R\in X_R,x_R\le y$，要么 $\exists y_L\in Y_L,x\le y_L$。前者说明 $y>L(x_R)$，与 $R$ 的定义矛盾。后者加上 $\exists x_L\in X_L,y_L<R(x_L)$ 说明 $x\le y_L\le x_L$，与 $x\nleq x_L$ 矛盾。 再**考虑 $L\ge R$ 的情形**。考虑归纳。 $L(x)=L$. 依定义，这当且仅当以下成立：数 $y>L$ 当且仅当 $y\ge x$。设 $y=(Y_L,Y_R)$。 $y\ge x$，若 $y>L$：若 $y>L$，则 $\forall x_L\in X_L$，有 $y>R(x_L)$，即 $y\nleq x_L$。又因 $L\ge R$，有 $y>R$，故 $\forall y_R\in Y_R,y_R>y>R$，依归纳假设有 $y_R\nleq x$，故 $y\ge x$。 $y\ngeq x$，若 $y<L$：若 $y<L$，则 $\exists x_L\in X_L$，满足 $y<R(x_L)$，即 $y\leq x_L\ngeq x$。 $R(x)=R$. 依定义，这当且仅当以下成立：数 $y<R$ 当且仅当 $y\le x$。设 $y=(Y_L,Y_R)$。 $y\le x$，若 $y<R$：若 $y<R$，则 $\forall x_R\in X_R$，有 $y<L(x_R)$，即 $y\ngeq x_R$。又因 $R\le L$，有 $y<L$，故 $\forall y_L\in Y_L,y_L<y<L$，依归纳假设有 $y_L\ngeq x$，故 $y\le x$。 $y\nleq x$，若 $y>R$：若 $y>R$，则 $\exists x_R\in X_R$，满足 $y>L(x_R)$，即 $y\ge x_R\nleq x$。 **定义 28.** 对于一个 Dedekind 分割 $q=(Q_L,Q_R)$ 和数 $x$，定义 $q+x=x+q=(\{q_L+x|q_L\in Q_L\},\{q_R+x|q_R\in Q_R\})$。 **定理 25.** 对于任意伪数 $x,y$，若 $x\le y$，则 $L(x)\le L(y),R(x)\le R(y)$。 **证明 25.** 设 $L(x)=(X_{LL},X_{LR}),L(y)=(Y_{LL},Y_{LR})$，则 $\forall z\in Y_{LR},z\ge y\le x$，故 $Y_{LR}\subseteq X_{LR}$，即 $L(x)\le L(y)$。 设 $R(x)=(X_{RL},X_{RR}),R(y)=(Y_{RL},Y_{RR})$，则 $\forall z\in Y_{RL},z\le x\le y$，故 $X_{RL}\subseteq Y_{RL}$，即 $R(x)\le R(y)$。 **定理 26. （平移定理）** 对于任何**短**伪数 $x$ 为 $(X_L,X_R)$，若 $x$ 不等于任何一个数，则对于任何数 $y$ 都有 $x+y=(\{x_L+y|x_L\in X_L\},\{x_R+y|x_R\in X_R\})$，且 $L(x+y)=L(x)+y,R(x+y)=R(x)+y$。 **证明 26.** 设 $y$ 为 $(Y_L,Y_R)$。后两者可以轻松由第一者、归纳假设和定理 23. 导出，因此只需要递归地证明第一者。 $x+y\le (\{x_L+y|x_L\in X_L\},\{x_R+y|x_R\in X_R\})$. 若不然，则以下三者至少有一成立：$\exists x_L\in X_L,x_L+y\ge (\{x_L+y|x_L\in X_L\},\{x_R+y|x_R\in X_R\})$，或 $\exists y_L\in Y_L,x+y_L\ge (\{x_L+y|x_L\in X_L\},\{x_R+y|x_R\in X_R\})$，或 $\exists x_R\in X_R,x+y\ge x_R+y$。但是第一者和第三者由对于任意伪数，有 $x_L\ngeq x,x\ngeq x_R$ 保证不成立，故只需考虑第二者。根据归纳假设，$R(x+y_L)=R(x)+y_L$，又依定理 23.，$R((\{x_L+y|x_L\in X_L\},\{x_R+y|x_R\in X_R\}))=\inf\limits_{x_R\in X_R}L(x_R+y)=y+\inf\limits_{x_R\in X_R}L(x_R)=R(x)+y$，因为 $R(x)+y_L<R(x)+y$，故第二者不成立。 $x+y\ge (\{x_L+y|x_L\in X_L\},\{x_R+y|x_R\in X_R\})$. 若不然，则以下三者至少有一成立：$\exists x_R\in X_R,x_R+y\le (\{x_L+y|x_L\in X_L\},\{x_R+y|x_R\in X_R\})$，或 $\exists y_R\in Y_R,x+y_R\le (\{x_L+y|x_L\in X_L\},\{x_R+y|x_R\in X_R\})$，或 $\exists x_L\in X_L,x+y\le x_L+y$。但是第一者和第三者由对于任意伪数，有 $x_L\ngeq x,x\ngeq x_R$ 保证不成立，故只需考虑第二者。根据归纳假设，$L(x+y_R)=L(x)+y_R$，又依定理 23.，$L((\{x_L+y|x_L\in X_L\},\{x_R+y|x_R\in X_R\}))=\sup\limits_{x_L\in X_L}R(x_L+y)=y+\sup\limits_{x_L\in X_L}R(x_L)=L(x)+y$，因为 $L(x)+y_R>L(x)+y$，故第二者不成立。 > 为什么要求是短伪数？如果是长伪数的话，$R(x)+y_L<R(x)+y$ 可能不成立，典型的例子是 $R(x)$ 的左/右集为 $0$ 的情况。 **定义 29.** 对于非负整数 $\alpha$，定义 $h(\alpha)=(\{h(\beta)|\beta<\alpha\},\{h(\beta)|\beta<\alpha\})$。 **定理 27.** 对于 $\alpha,\beta$，有 $h(\alpha)+h(\beta)=h(\alpha\oplus \beta)$，其中 $\oplus$ 表示异或和。$h(\alpha)\le h(\beta)$ 当且仅当 $\alpha=\beta$。对于 $L\subseteq\N$，$(\{h(\gamma)|\gamma\in L\},\{h(\gamma)|\gamma\in L\})=h(\operatorname{mex}(L))$。 **证明 27.** 这即 Sprague–Grundy 定理所揭示的。 ## 题解 有了定理 22.，只需要算出每个博弈对应的超现实数，再区间求和判断与 $0$ 的关系即可。有了定理 21.、定理 26.，我们可以方便地计算一个博弈对应的超现实数。定义 $f_{p,q}(H,W)$ 表示参数 $(p,q,H,W)$ 对应的长方形对应的超现实数。则经过一定的计算我们不难找出规律。 **定理 28.** 若 $HW$ 为奇数，则 $f_{1,1}(H,W)=h(A(H)\oplus A(W))$，否则 $f_{1,1}(H,W)=h((A(H)\oplus A(W))+1)$。其中，$A(x)$ 表示 $x$ 的非 $2$ 质因子个数。（重复算多次） **证明 28.** 若 $HW$ 为奇数，每次分裂出奇数个，相当于分裂出 $1$ 个，此时就是博弈的笛卡尔积，不难证明单个博弈的值为 $A$。否则，每一步多一个走向 $0$ 的选项，因此可以归纳证明整体的 $\operatorname{mex}$ 会多 $1$。 **定理 29.** 设 $H,W$ 的质因数分解 $H=p_1p_2\cdots p_u,W=q_1q_2\cdots q_v$，其中 $p,q$ 为单调不降的质数。则 $$ f_{0,0}(H,W)=\begin{cases} 0&u=v\\ g\left(\sum\limits_{i=0}^{u-v-1}\prod\limits_{j=0}^{i-1}p_{u-j}\right)&u>v\\ g\left(-\sum\limits_{i=0}^{v-u-1}\prod\limits_{j=0}^{i-1}q_{v-j}\right)&u<v \end{cases} $$ **证明 29.** 根据定理 21. 和一些贪心策略易得。 那么 $f_{1,0}$ 呢？好像要麻烦一点了，因为它们形如 $g(A)+h(B)$。但是可以发现，$W>1$ 时，转移时左集中不被偏序的元素是一样的。因此可以导出—— **定理 30.** $g(A_1)+h(B_1)\le g(A_2)+h(B_2)$ 当且仅当 $A_1<A_2$ 或 $A_1=A_2,B_1=B_2$。 **证明 30.** 不妨设 $A_1=B_1=0$。则，$A_2=0$ 时显然。否则考察其 $R$ 集合，根据平移定理显然。 **定理 31.** $f_{1,0}(p,q)=qf_{0,0}(p,1)+f_{1,1}(1,q)$，其中 $qx$ 表示 $q$ 个 $x$ 相加。 **证明 31.** 当 $q=1$ 时是显然的，因为递推式一样。当 $q>1$ 时，根据证明 29. 中的贪心策略，左玩家转移到 $lf_{1,0}(p/l,q)$ 一定是不如 $lf_{1,0}(p,q/l)$ 优的。这时两边是对称的，不难发现 $f_{1,0}(p,q)=qf_{0,0}(p,1)+c(q)$，而显然 $c(q)$ 的递推式和 $f_{1,1}(1,q)$ 相同。 **定理 32.** $f_{0,1}(p,q)=pf_{0,0}(1,q)+f_{1,1}(1,p)$，其中 $px$ 表示 $p$ 个 $x$ 相加。 **证明 32.** 和证明 31. 同理。 因此我们可以求出每个长方形代表的超现实数，进而区间求和，根据定理 30. 判断胜负！于是本题就做完了。 ## 代码 ```cpp #include <bits/stdc++.h> using namespace std; int n,a,b,h,w,q,l,r; int f[100005],g[100005],p[100005],d[100005],c; bool np[100005]; long long x[100005],y[100005]; int main() { ios_base::sync_with_stdio(false);cin.tie(0); cin>>n; f[1]=0;g[1]=0; for(int i=2;i<=100000;++i) { if(!np[i]) { p[++c]=i;f[i]=int(i>2);g[i]=1;d[i]=i; } for(int j=1;j<=c;++j) { int ret=i*p[j]; if(ret>100000)break; np[ret]=true; f[ret]=int(j>1)+f[i]; g[ret]=i+g[i]; d[ret]=p[j]; if(i%p[j]==0)break; } } for(int i=1;i<=n;++i) { cin>>a>>b>>h>>w; x[i]=0;y[i]=0; if(a==1&&b==1) { y[i]=(f[h]^f[w])+int(h%2==0||w%2==0); } else if(a==0&&b==0) { while(h>1&&w>1) h/=d[h],w/=d[w]; if(h>1) x[i]=g[h]; else x[i]=-g[w]; } else if(a==1&&b==0) { x[i]=w*1ll*g[h]; y[i]=f[w]+int(w%2==0); } else { x[i]=-h*1ll*g[w]; y[i]=f[h]+int(h%2==0); } x[i]+=x[i-1]; y[i]^=y[i-1]; } cin>>q; while(q--) { cin>>l>>r; long long X=x[r]-x[l-1],Y=y[r]^y[l-1]; if(X<0||(X==0&&Y==0)) cout<<"No\n"; else cout<<"Yes\n"; } return 0; } ``` ## 后记 非常感谢 @[Galois_Field_1048576](https://www.luogu.com.cn/user/360265)、@[ProjectCF](https://www.luogu.com.cn/user/168596) 和 @[zhuzhu2891](https://www.luogu.com.cn/user/515385) 对本文的帮助！（按字典序排序） 非常感谢能够看完这么一篇长文的你！接下来，你可以再看看 [[ABC229H] Advance or Eat 并不是题解而是超现实数入门](https://www.luogu.com/article/tvv7igm2) 的定理 21. 到定理 24. 和“更多”部分。如果还不够，欢迎阅读 On Numbers And Games（见参考文献）！ 非常感谢耐心审核到这里的题解审核志愿者，您辛苦了！ 参考文献： Donald E. Knuth, Surreal numbers, Addison-Wesley, 1974 John Conway, On Numbers And Games, 1976. 马耀华, 浅谈超现实数与不平等博弈, IOI2021 中国国家候选队论文集, 2021.