P10222 最长待机 不很是题解而是序数理论入门

· · 题解

这篇“题解”实际上是用这题来引入无限序数的概念，并最终给出这题的弱化版本（不带修改）的解。

为了更好说明本题的需要，本题定义的序数的加法和乘法的顺序和正常的序数加法乘法是相反的。

因为我是数据结构低手，所以我并不知道如何把这个结论应用到正解。

根据定义，Sleep++ 程序的函数的调用关系形成了一棵有向树。

如果一个 Sleep++ 程序只有 e=0 的函数，则所有函数的运行时间是某个固定的有限值，这个有限值也不难算出。

但是，一旦某个函数的 e=1，它本身以及所有直接或间接调用它的函数，由于输入值是任意的，于是运行的时间可以任意长。注意，任意长不是无限长，最终一定会停止。

题目的要求促使我们想一种办法比较两个函数的运行时间。

但是两个任意长怎么比较呢？无论其中一个多长，另一个总是可以更长。

最基本的问题是，一个 e=1 的空函数需要的运行时间应该如何度量？

它并不是无穷大，最终一定会停止；它也不是有限的正整数，这个程序可以跑得比任意正整数还长。

这促使我们发明一个新的记号来代表它：\omega。\omega 的含义即为“大于任意正整数的最小数”。

需要跑 \omega 秒的意思是，输入一个任意正整数让 \omega 坍缩到那个正整数。

于是我们可以构造出长度形如 $3+\omega$，$\omega+5+\omega+\omega+6$ 等的程序了。 $\omega$ 上各运算律是否仍然成立还是未知的，所以别急着化简。 --- 既然有了 $\omega$，那有没有比 $\omega$ 更慢的呢？比如……$1+\omega$？ 它的含义很明显，先等 $1$ 秒，然后输入一个数让 $\omega$ “坍缩”到那个数，最后结束。 这当然是比 $\omega$ 要大的：你有时间看一眼对方声明的数，自己声明更大的就行了。 --- 这里你会开始注意到新运算的一个不寻常之处：加法不再交换。 考虑 $\omega+1$。它的含义是，先输入一个数让 $\omega$ “坍缩”到那个数，等那么多秒，再等一秒，才结束。 问题是这和多输入 $1$ 没有任何区别！于是 $\omega+1=\omega<1+\omega$。 这说明，高阶项会吸收掉右侧的低阶项。 --- 有了 $1+\omega$ 自然就能有 $2+\omega,3+\omega,4+\omega,\cdots$，最终，我们会到达 $\omega+\omega$，或 $2\omega$。 $2\omega$ 的含义也是很显然的：你可以声明一次，过那么久，然后声明第二次，再过那么久，结束。 以此类推，还可以有 $3\omega,4\omega,\cdots$，最终到达 $\omega^2$。 一个 $\omega^2$ 相当于一个二阶声明，它声明了接下来我会进行几次声明（，还可能再附带一些常数）。 --- 同样很自然地，$e=1$ 的非空函数，其结果应该是各子函数按顺序加和，最后左乘 $\omega$。 带入游戏推断一下以后，你会发现，$\omega(3+2\omega)=\omega^2$。 这是因为，进行左边的 $\omega$ 对应的二阶声明后，虽然看起来获得了两倍的声明次数还多了一点常数，但是你本来就可以声明那么多次数，于是就和 $\omega^2$ 没有区别了。 --- 有了 $\omega^2$ 再套一层就能有 $\omega^3$，相当于一个三阶声明，声明接下来使用二阶声明的次数（，可能附带几次一阶声明和一些常数）。 同样就能有 $\omega^4,\omega^5$，等等。这样套下去可以得到任意次数。 虽然已经和本题没关系了，不过这样就能达到 $\omega^\omega$，相当于第一步进行元声明，声明想要获得一个多少阶的声明。 --- 题目的机制已经完全搞清楚了： - 对于空函数，$e=0$ 的时长是 $1$，$e=1$ 的时长是 $\omega

按照这个步骤计算一遍就能得到任意函数的运行时长。

题目的要求是构造一个函数最少的程序让游戏公平。

这也很简单。我们知道升阶只会保留阶数信息，于是每一项最快都由直接升阶若干次得到。那么 \sum a_i\omega^i 就至少需要 1+\sum \max(i,1)a_i 个函数，除了只有系数为 1 的一项的特殊情况以外。

重申：为了更好说明本题的需要，本题定义的序数的加法和乘法的顺序和正常的序数加法乘法是相反的。

重申2：因为我是数据结构低手，所以我并不知道如何把这个结论应用到正解。我在讨论区看到了一个把这个做法应用到正解的方法，如有兴趣可以查看。

拓展阅读：

【中字】ω步杀，无限象棋的非凡现象

【中字】ω^3、ω^4、ω^ω步杀……关于持续最久的无限象棋对局的研究

这两个视频讨论的 \omega 步杀是我看到过的最好的关于“\omega 是什么”的解释，对于理解之前的说明有一定帮助，视频本身也很有趣。