题解：P12668 「TFXOI Round 2」命中注定的抉择

可爱大黄兔 · 2025-05-31 17:50:11 · 题解

解题思路

首先根据公式 a_i = (a_{i-1} - d) ^ x 计算每一层的盒子数，注意从第二层开始计算。使用 op 表示状态。然后逐层处理：若 op=1：计算全黑数量 ot = \min(a_i-1, A)。令 l = A - ot，sl = s - ot，若 l = 0：则剩余全白，则 s = a_i，A = ot。若 l = sl：则剩余全黑，则 s = a_i，A = a_i。若 op=2：计算全黑数 ot = \min(a_i-1, s-1)。接下来可知剩余节点数 t = (s-1) - ot。然后更新两种节点都可能存在的概率 v = (t + v) \times (t+1)^{-1}。 最后处理完所有层后，根据最终状态计算答案：

• 若 op=1，概率为 A \times s^{-1}。
• 若 op=2，概率为 ((s-1) + v) \times s^{-1}。

代码

用费马小定理求逆元，代码就不放了（怕小鞋神抄）。初始复杂度 O(\log_{} \bmod\times k)，用 map 优化可以防止 TLE。