加密货币灯：题解

思路

把所有灯最终被选择的先后顺序看成一个等概率随机排列。设随机变量 $T$ 表示装置停止时已经点亮的灯数。对非负整数随机变量使用尾和公式：

$$\mathbb E[T]=\sum_{m\ge 0}\Pr(T>m).$$

$T>m$ 等价于前 $m$ 盏被点亮的灯仍未触发停止条件。两个位置能同时存在于一个长度为 $k$ 的区间中，当且仅当它们的距离小于 $k$。因此，前 $m$ 个位置按从小到大排列后，相邻位置的距离都必须至少为 $k$。

从 $n$ 个位置中任取 $m$ 个的方案数为 $\binom nm$。若选中的位置是

$$x_1<x_2<\cdots<x_m,$$

令 $y_i=x_i-(i-1)(k-1)$，则 $1\le y_1<\cdots<y_m\le n-(k-1)(m-1)$。所以合法集合数为

$$\binom{n-(k-1)(m-1)}m.$$

于是

$$\Pr(T>m)= \frac{\binom{n-(k-1)(m-1)}m}{\binom nm},$$

只需枚举仍满足 $n-(k-1)(m-1)\ge m$ 的 $m$。

做法

子任务 1 可以枚举全部灯的排列，模拟第一次出现距离小于 $k$ 的两盏灯，累加停止位置，复杂度为 $O(n!n^2)$。

子任务 2 可以枚举全部位置子集，检查相邻选中位置的距离是否至少为 $k$，按子集大小统计合法集合数，再代入尾和公式，复杂度为 $O(2^n n)$。

满分做法预处理阶乘和逆阶乘，在 $O(1)$ 时间计算组合数。对每组询问依次枚举 $m$，把上式的概率加入答案。由于 $m$ 每次递增，枚举次数不超过 $n$。

模意义下除以 $\binom nm$，等价于乘上

$$\binom nm^{-1}=m!(n-m)!(n!)^{-1}.$$

复杂度

预处理复杂度为 $O(N)$，其中 $N$ 是所有询问中的最大 $n$。每组询问的时间复杂度为 $O(n)$，空间复杂度为 $O(N)$。