Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2) E.Crypto Lights(组合数学+期望)

题目

t(t<=10)组样例，每次给出一个n,k(2<=k<=n<=1e5)

表示1,2,...,n位置上每个位置放置了一盏熄灭的灯，

你等概率地选择一盏熄灭的灯并点亮，并等概率地从熄灭地灯里选一盏且点亮，

特别地，如果此刻存在两盏灯的距离小于等于k，则游戏终止

求游戏终止时，操作的灯的数量的期望

思路来源

https://blog.csdn.net/Tan_tan_tann/article/details/117430238

https://blog.csdn.net/m0_51068403/article/details/117606131

题解

考虑对于这个样例，竖着统计方案数对期望的贡献，

即统计第i步时游戏还没结束的方案数，其贡献为1，

再除以此时总方案数，就是第i步的期望贡献，

也可以认为是，统计第i步游戏没结束的方案数，除以第i步的总方案数，即得第i步的概率，

由于此刻贡献为1，直接把概率加到期望里即可

感觉下面这个好理解一点，

即第一步的时候，对于1，2，3，有100%的概率不会终止，

第二步的时候，对于12,13,23,21,23,31,32来说，有33%的概率不会终止，以此类推

设到第i步时游戏还没有终止，则前i步两两之间的距离>=k

可以认为两两之间预先有k-1盏灯，并把(i-1)*(k-1)盏灯从n盏灯里拿掉，

从剩下的n-(i-1)*(k-1)个11111111111111的灯里选i盏，

对于选出来的一种方案来说，让两盏灯之间插入k-1盏灯，再插入原来的两个1之间的1的灯数，

即可唯一对应一种方案，乘上顺序i!，除以前i步有序方案数n*(n-1)*...*(n-i+1)

是参考的思路来源的这个推法，感觉说的非常清楚

最终，对答案+1即可

这是因为，考虑到每一种合法方案来说，

其减1都是一个两两间大于k的方案

参考法二，本题也可以从第i步有多少方案恰停止来考虑，是类似的

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10,mod=1e9+7;
int t,n,k,ans,now,fac[N],finv[N];
void init(){
	fac[0]=finv[0]=fac[1]=finv[1]=1;
	for(int i=2;i<N;++i){
		finv[i]=1ll*(mod-mod/i)*finv[mod%i]%mod;
		fac[i]=1ll*fac[i-1]*i%mod;
	}
	for(int i=2;i<N;++i){
		finv[i]=1ll*finv[i-1]*finv[i]%mod;
	}
}
int C(int n,int m){
	if(n<0 || m<0 || n<m)return 0;
	return 1ll*fac[n]*finv[n-m]%mod*finv[m]%mod;
}
int invC(int n,int m){
	if(n<0 || m<0 || n<m)return 0;
	return 1ll*finv[n]*fac[n-m]%mod*fac[m]%mod;
}
int main(){
	init();
	scanf("%d",&t);
	while(t--){
		scanf("%d%d",&n,&k);
		ans=0;
		for(int i=1;i<=n;++i){
			if(n-(i-1)*(k-1)<i)break;
			ans=(ans+1ll*C(n-(i-1)*(k-1),i)*invC(n,i)%mod)%mod; 
		}
		printf("%d\n",(ans+1)%mod);
	}
	return 0;
}