题解 P8348 【「Wdoi-6」未知之花魅知之旅】

· · 题解

以下称 a=a_0,b=a_1。只讨论 a,b,x,y 均不小于 k 的情况。

对于连续两项 a_{i-1},a_i，知道 a_{i+1} 至多有两种可能：

称可能性 1 为加操作，可能性 2 为减操作。

下面开始解决此问题。

首先注意到一件事：以 a,b 为开头的数列中存在连续的 x,y 和以 y,x 为开头的数列中存在连续的 b,a 是等价的。

事实上，在这个观察中还包含一件事，那就是

当且仅当存在 c,d 使得以 a,b 开头能得到相邻的 c,d，以 y,x 开头能得到相邻的 d,c 时，以 a,b 开头能得到相邻的 x,y。

这能够让我们寻求一对更简单的 c,d 来刻画 a,b 开头的这个数列的根本性质。

由于题目中给出了一个 k 作为限制，因此自然地想到找整个数列中最小的一组 c,d。这个最小的刻画条件有多种，可以选取“和最小”为条件。

接下来我们注意到一个事实：和最小的 c,d 下一步一定不能是减操作。为了不能是减操作，此时要求 \lvert c-d \rvert<k，我们称使得 \lvert c-d \rvert<k 的 (c,d) 是极小的，下证明一个结论：对于特定的 a,b，能够达到的极小相邻 c,d 是唯一的。

事实上注意到一次加后紧跟的两次减会使得数列当前的最后两项不变，后续操作也不受影响，如下：

a,b,a+b,a,b,\dots.

如果一次加操作后至多连续一次减操作，我们证明最终得不到极小相邻 c,d。假设这样操作得到了 c,d 是极小的，则考虑 c,d 前的操作。若是一次加操作，则有前一项为 \lvert c-d \rvert \ge k，故非极小。若是一次减操作，则再进行一次减操作后与去掉最后的一次减操作与一次加操作时相同，故非极小。

故达到的极小相邻 c,d 之前一定经过了两次连续的减操作，则可以与前面的一次加操作抵消。如此抵消下去只要没有将加操作抵消完，就一定会出现一次加后至多连续一次减的情况，矛盾！故加操作一定会被全部抵消。

若一直进行减操作，则显然得到的 c,d 是唯一的。操作到不能再操作即为所求。

然后用类似求 \gcd 的欧几里得算法即可解决此题。

upd 2022/5/22

感觉上面的证明过程不算很完整，还有一点并不非常显然的东西需要说明一下。于是来补一发。

必要性如上证明已经是完备的。下只证充分性。

首先有上面证明出的结论：由一个给定的 a,b 只能到唯一的极小 c,d。

用反证法，如果存在 a,b 能够到达 x,y 且 a,b 到达极小 c,d，y,x 到达的极小并非 d,c。根据结论 y,x 不能到达 d,c。

我们考虑两种情况：

那么显然 c,d 能到达 x,y，故我们要求 y,x 能到达 d,c。

那么显然我们要求 x,y 能到达 c,d。由于题设操作可逆，因此 c,d 能到达 x,y，即 y,x 能到达 d,c。

故 y,x 能到达 d,c。与反证假设矛盾。结论证毕。