CF1523E Crypto Lights

题目大意

n 个台灯初始时都是暗的,每次等概率随机一个暗台灯将其点亮,若点亮后存在一个长度为 k 的连续段有大于一个台灯被点亮则立刻停止,求期望点亮多少台灯。答案对 10^9+7 取模。

2≤k≤n≤10^5

Solution

从期望定义出发,令在开第 i 盏灯的时候游戏结束的概率为 p_i

则期望 E 有
E = \sum^n_{i=1} p_i \times i
考虑令
a_i = \sum_{j=i}^n p_i

也就相当于 a_i{p_1,p_2,\dots,p_n} 的一个后缀和。

则有
E=\sum_{i=1}^n a_i
结合 a_i = \sum_{j=i}^n p_i,思考 a_i 的定义,则发现 a_i 可以表示按下第i-1 盏灯时,游戏仍未结束(但是可能在 [i,n] 任何一盏灯中结束)的概率。

考虑计算 a_ia_i 为 按下第i-1 盏灯时,游戏仍未结束的方案数 除以 按下 i-1 栈灯的所有情况


a_i = \frac{A}{C^{ i-1}_{n}}
考虑计算 按下第i-1 盏灯时,游戏仍未结束的方案数,即A。

按下的 i-1 盏灯之间的距离必定是大于等于 k ,也就是说每个间隔之间至少有 k-1 栈暗灯,一共有 i-2 个间隔,也就是说至少有 (k-1)\times(i-2) 栈灯是灭掉,并且每个间隔至少有 k-1 栈灭掉的灯。

那我们考虑先去掉这 (k-1)\times(i-2),还剩下 n-(k-1)\times(i-2) 灯,在这当中选 i-1 栈灯点亮,然后在每两个刚点亮的灯之间的间隔,共 i-2 个间隔中,每个间隔都放 k-1 个灭掉的灯,这样就可以保证方案一定合法。并且方案数就是

$C^{i-1}{n-(k-1)\times(i-2)}$
a_i=\frac{C^{i-1}_{n-(k-1)\times(i-2)}}{C^{ i-1}_{n}}

分类: 期望组合

0 条评论

发表评论

Avatar placeholder

您的电子邮箱地址不会被公开。 必填项已用*标注