CF1523E Crypto Lights 做题记录

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

$2\le k\le n\le 10^5$。

考虑期望的本质，设 $p_i$ 为恰好在点亮第 $i$ 个台灯后停止，则答案为：

$\sum\limits_{i=1}^{n} i\cdot p_i$

发现若设 $s_i=\sum\limits_{j=i}^{n}p_j$ 即 $p$ 的后缀和，那么答案等于：

$\sum\limits_{i=1}^{n} s_i$

发现 $s_i$ 可以看作是点亮了前 $i-1$ 个台灯仍未停止的概率，所以 $s_i=\frac{\binom{n-(k-1)(i-2)}{i-1}(i-1)!}{\binom{n}{i-1}(i-1)!}=\frac{\binom{n-(k-1)(i-2)}{i-1}}{\binom{n}{i-1}}$。

其中分子的计算方式是在确定完亮的台灯的位置后在相邻两个亮的台灯之间插入 $k-1$ 个暗的台灯。

那么直接计算即可，不过 $s_1=1$ 要特判。时间复杂度 $O(n)$，代码如下：

#include <iostream>
#include <cstdio>

using namespace std;

const int S=100005,p=1000000007;

int n,k;
int fra[S],inv[S];

inline int qpow(int x,int y)
{
	int res=1;
	for(;y>0;y>>=1,x=1ll*x*x%p) res=y&1?1ll*res*x%p:res;
	return res;
}

inline int C(long long n,int m)
{
	if(n<0||m<0||n<m) return 0;
	return 1ll*fra[n]*inv[n-m]%p*inv[m]%p;
}

int main()
{
	fra[0]=1;
	for(int i=1;i<=S-3;i++) fra[i]=1ll*fra[i-1]*i%p;
	inv[S-3]=qpow(fra[S-3],p-2);
	for(int i=S-3;i>=1;i--) inv[i-1]=1ll*inv[i]*i%p;
	int T;
	scanf("%d",&T);
	while(T-->0)
	{
		scanf("%d%d",&n,&k);
		int ans=0;
		for(int i=1;i<=n;i++)
		{
			int si=i==1?1:1ll*C(n-1ll*(k-1)*(i-2),i-1)*qpow(C(n,i-1),p-2)%p;
			ans=(ans+si)%p;
		}
		printf("%d\n",ans);
	}
	return 0;
}