最核心的思维主线

大 KK → 终局 → 零化 → 分层 → 下沉 → 坍塌 → 降维 → 快进

这道题最重要的不是最后的公式，而是发现：

原本有 10510^5 个数，但真正需要长期处理的数会越来越少。

原题链接：P12632 [ICPC 2025 NAC] This Is Sparta!

一、我最开始走的路线

看到：

K≤1018K\le 10^{18}

我立即想到：

大 KK → 不能模拟 → 推递推 → 找闭式

排序后，一轮操作满足：

b1=a1,bi=ai−bi−1.b_1=a_1,\qquad b_i=a_i-b_{i-1}.

继续展开，可以得到交错和，也可以发现奇数位、偶数位分别有序。

但是每轮结束后都要重新排序。

排序会打乱元素的位置，因此单轮递推无法直接扩展成 KK 轮闭式。

这条路最终断在：

递推 → 排序 → 断裂

二、真正重要的苗头：后期会有很多 00

我当时其实短暂想到过：

后面是不是会出现很多 00？

但因为没有立刻得到证明，就把这个想法放掉了。

实际上，00 是一个不可逆状态：

0→0.0\rightarrow0.

因此：

零的数量单调不减\boxed{\text{零的数量单调不减}}

等价地：

正数的数量单调不增\boxed{\text{正数的数量单调不增}}

这说明问题的有效规模可能不断缩小。

此时最应该追问的不是：

怎样快速计算很多轮？

而是：

很多轮以后，还剩多少个数需要计算？

三、直接研究“变成 00”太难，就先研究“下降一层”

把正数按照二进制数量级分层：

[1,2),[2,4),[4,8),…[1,2),[2,4),[4,8),\ldots

考虑同一层中的两个相邻数：

ai,ai+1∈[2j,2j+1).a_i,a_{i+1}\in[2^j,2^{j+1}).

下一轮中，如果

bi<2j,b_i<2^j,

那么 bib_i 已经下降一层。

否则 bi≥2jb_i\ge 2^j，于是：

bi+1=ai+1−bi<2j+1−2j=2j.b_{i+1}=a_{i+1}-b_i<2^{j+1}-2^j=2^j.

那么 bi+1b_{i+1} 一定下降一层。

所以：

同层相邻的两个数，至少有一个会下沉\boxed{\text{同层相邻的两个数，至少有一个会下沉}}

也就是：

同层 → 相减 → 下沉

不断重复：

下沉 → 下沉 → 下沉 → 零化

所有数都不超过 101810^{18}，二进制层数只有约 6060 层。

因此，大量元素会不断下沉，最终变成 00。

这就是数据坍塌。

四、坍塌之后再快进

原问题看起来有：

N=105N=10^5

个状态。

但模拟足够多轮后，只会剩下至多三个正数。如果此时 KK 还没有耗尽，就可以转入常数维处理。

于是：

高维 → 坍塌 → 低维

只剩三个数：

a≤b≤ca\le b\le c

且顺序暂时不变时，经过 tt 轮：

[a,  b−ta,  c−tb+t(t+1)2a].\left[ a,\; b-ta,\; c-tb+\frac{t(t+1)}2a \right].

这时才使用闭式批量跳跃。

只剩两个数时：

[a,b]→[a,b−a],[a,b]\rightarrow[a,b-a],

就是欧几里得算法。

因此完整解法不是一开始就快进，而是：

先模拟坍塌，再低维快进。

这道题真正应该记住什么

不是记住“二进制分桶”。

而是记住这个触发：

超大轮数 + 不可逆变化 → 先看终局

发现死亡状态后：

死亡 → 活跃数

无法证明立刻死亡时：

死亡距离 → 分层

发现层级不断下降后：

分层 → 下沉 → 坍塌

最后才是：

坍塌 → 降维 → 快进

最终主线

大 KK → 终局 → 零化 → 分层 → 下沉 → 坍塌 → 降维 → 快进

再压缩一次：

终局 → 下沉 → 坍塌 → 快进

这道题不是在问：

怎样快速执行 101810^{18} 轮？

而是在问：

执行不了多少轮以后，原来的 10510^5 个状态还剩下几个？