P12632 This Is Sparta!：数据会自己坍塌

最核心的思维主线

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

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

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

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

一、我最开始走的路线

看到：

K\le 10^{18}

我立即想到：

大 $K$ → 不能模拟 → 推递推 → 找闭式

排序后，一轮操作满足：

b_1=a_1,\qquad b_i=a_i-b_{i-1}.

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

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

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

这条路最终断在：

递推 → 排序 → 断裂

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

我当时其实短暂想到过：

后面是不是会出现很多 $0$ ？

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

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

0\rightarrow0.

因此：

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

等价地：

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

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

此时最应该追问的不是：

怎样快速计算很多轮？

而是：

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

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

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

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

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

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

下一轮中，如果

b_i<2^j,

那么 $b_i$ 已经下降一层。

否则 $b_i\ge 2^j$ ，于是：

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

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

所以：

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

也就是：

同层 → 相减 → 下沉

不断重复：

下沉 → 下沉 → 下沉 → 零化

所有数都不超过 $10^{18}$ ，二进制层数只有约 $60$ 层。

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

这就是数据坍塌。

四、坍塌之后再快进

原问题看起来有：

N=10^5

个状态。

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

于是：

高维 → 坍塌 → 低维

只剩三个数：

a\le b\le c

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

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

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

只剩两个数时：

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

就是欧几里得算法。

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

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

这道题真正应该记住什么

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

而是记住这个触发：

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

发现死亡状态后：

死亡 → 活跃数

无法证明立刻死亡时：

死亡距离 → 分层

发现层级不断下降后：

分层 → 下沉 → 坍塌

最后才是：

坍塌 → 降维 → 快进

最终主线

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

再压缩一次：

终局 → 下沉 → 坍塌 → 快进

这道题不是在问：

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

而是在问：

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