不知道题解

· · 题解

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

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

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

说明一下为什么。首先可以发现，在每次第 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 号不被摸的概率，则：

由定义可发现 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 ，再后缀积处理一遍就可以做完了。
于是就结束啦。