题解：P10539 [APIO2024] 魔术表演

· · 题解

APIO2024，忆昔当年泪不干。

这个题的解决思路有两种，一种是保存完整的信息不要让信息被删干净，另一种是保存一些有效信息通过删除后剩余的有效信息还原原数。

第一个思路的一种可行做法为 k 进制拆分，先对 X 拆位，每一位连向代表 0 \sim k - 1 的点，多连几遍。随机删点的情况下正确率非常高。

但交互库可能会采取某种特殊策略删点，比如删除某个点连出去的所有边之类的。这样就有很大的可能会丢失信息。

多做几次随机置换能降低丢失信息的概率，最后能不能过比较吃运气。

由这个做法可以延伸到第二个思路的类似做法：我们对 X 做多次 k 进制拆分，每次取不同的 k。最后就算删除了相当一部分信息，我们仍然能从剩余的信息里还原出原来的 X。

这个做法可行但很麻烦，考虑一个更简单的做法。

把 k + 1 连向 X \bmod k + 1，最后 exCRT 还原一下即可（实际上直接暴力还原复杂度也是对的）。

设保留下来的边里的更大的数为 x_i，那么最后一定能还原出一个小于所有 x - 1 的最小公倍数的解。

我们只要保证这个最小公倍数大于 10^{18} 即可，为了保证正确性，要把 n 取大一点。