自动搬运

查看原文

来自洛谷，原作者为

	FLY_lai Nijika Ijichi

搬运于2025-08-24 23:11:13，当前版本为作者最后更新于2025-02-20 21:04:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

（下称不知道喜欢的格子为喵格）
首先，考虑一个子情况： $k=0$ ，此时，容易发现每次都是当前位于第一格的猫被摸，即最后一格的猫必定没摸。
也可以发现在 $k$ 更大的情况下，随着猫数的减少，被启用的喵格实际上是在不断减少的，在猫数少于 $t_1$ 个时，相当于退化成了 $k=0$ 的情况，即对所有猫，不被摸的条件是：

• 在猫数少于 $t_1$ 个时，自身位于所有猫中编号最大的一格。

以原题中样例 #3 为例。
先看第 $8$ 只猫，它在所有猫中格子编号永远是最大的，因而它只需要等到场上只剩 $t_1-1=2$ 只猫为止便会不被摸。
考虑猫怎么样会被摸。很明显，当且仅当它在一个喵格上，且被抽中，它才会被摸。同时由于我们讨论的是 $8$ 号不被摸的概率，当 $8$ 号不在喵格上时，谁被摸其实都是无所谓的（反正不是 $8$ 号，对 $8$ 号的不被摸概率没有影响），从结果上看只是把 $8$ 号往前推了一格。
如果 $8$ 号能留到只剩 $2$ 只猫，它一定会经过所有喵格一次（除了 $t_0$）。容易发现，若是 $8$ 号没被摸，由于它后面不可能有猫了，它后面的喵格一定没有被启用；即令它及它前面的喵格个数为 $v_i$ ，则：

• 若 $8$ 号站在喵格上，它在这格上被摸的概率是 $\frac{v_i-1}{v_i}$ 。

再由于它会经过 $t_1\sim t_3$ 三个喵格，它在三个喵格上都不被摸下来的概率是 $\frac{3}{4}\times\frac{2}{3}\times\frac{1}{2}=\frac{1}{4}$ 。
这个结论明显是可以推广的：

• 第 $n$ 个猫不被摸的概率是 $\frac{1}{k+1}$ 。

说明一下为什么。首先可以发现，在每次第 $n$ 个猫站在喵格上时，它及它前面的喵格个数一定是正好比上次少了一个的，根据上面的公式推一下便可以得到这个结论。

再来看第 $7$ 个猫。它的不被摸条件有所变更：等到只剩两个猫自然是前提，但由于它不是最后一个猫，可能它在等到最后两个猫时不是最后一个猫，因此它后面的猫还要全部被摸才行。
它等到只剩最后 $2$ 个猫的概率和上面算法一样，不被摸的概率是 $\frac{1}{3}$ ；问题是 $8$ 号被摸的概率。它一直等过它及它前面的三个喵格的概率是 $\frac{1}{4}$ ，那么它在这三个喵格中的一个被摸的概率便是 $1-\frac{1}{4}=\frac{3}{4}$ 。那么 $7$ 号不被摸下来的概率便是 $\frac{1}{3}\times\frac{3}{4}=\frac{1}{4}$ 。
不过在喵格相邻的情况下，可能存在非最后一个猫的后面的喵格仍启用的问题。其实这也是没有影响的，因为对一个猫本身撑过某个喵格的概率来说，要么就是这个猫在这里被摸，要么就是它离开这个格子。而若是它身后的喵格被启用，其实对这个猫相当于这次什么都没发生，同时下一次这两种情况的比例还是相同的，因此从结果上看仍是一样的。
在 $6$ 号身上便好套用了：它通过前两个喵格的概率是 $\frac{1}{3}$ ，后面两个猫被摸的概率分别是 $\frac{2}{3}$ 与 $\frac{3}{4}$ ，概率便是 $\frac{1}{6}$ 。
然而为什么对于 $7$ 号套用的不是用 $1$ 减去它的不被摸概率 $\frac{1}{4}$ 呢？因为在 $7$ 号算的是它不被摸且 $8$ 号被摸的概率，而在 $6$ 号的计算中只需计算 $7$ 号被摸的概率即可，不需要让 $8$ 号再被摸一次。
那么通用公式便可以被推出来了：仍令 $v_i$ 为第 $i$ 格及其前面的喵格数量，同时令 $p_i$ 为 $i$ 号不被摸的概率，则：

• $p_i=\frac{1}{v_i}\times\prod_{j=i+1}^{n}\frac{v_j-1}{v_j}$

由定义可发现 $v_1=1$ 。
同时再顺便说明一下为何 $\sum p_i=1$ 。不如用一个较小的例子（ $n=3$ ）来演示为什么 $\sum p_i=1$ ：
$ \begin{aligned} \sum p_i&=\frac{1}{v_1}\times\frac{v_2-1}{v_2}\times\frac{v_3-1}{v_3}+\frac{1}{v_2}\times\frac{v_3-1}{v_3}+\frac{1}{v_3}\\ &=\frac{v_2-1}{v_2}\times\frac{v_3-1}{v_3}+\frac{1}{v_2}\times\frac{v_3-1}{v_3}+\frac{1}{v_3}\\ &=\frac{v_3-1}{v_3}+\frac{1}{v_3}\\ &=1 \end{aligned} $

（第一步中，由于 $v_1=1$ ，第一项的 $\frac{1}{v_1}$ 能被抵消；从第二步开始，每一步中选择前两项合并，可以发现这样的合并方式一定能持续到化简完，便有 $\sum p_i=1$ ）

具体实现上，可以先处理逆元以及 $v_i$ ，再后缀积处理一遍就可以做完了。
于是就结束啦。