另类推柿子 Crypto Lights
Crypto Lights
大意：
有 n 个台灯初始时都是暗的，每次等概率随机一个暗台灯将其点亮，若点亮后存在一个长度为 k 的连续段有大于一个台灯被点亮则立刻停止，求期望点亮多少台灯。答案对1e9+7 取模
思路：
没见过这样子的推柿子的题，也算是开开眼了
考虑一个非常正确的答案
,其中pi表示第i次结束的概率，
显然这就是期望的定义求法。但是这样一个式子在大多数时候并不能带给我我们实质性的进展，因为它没有什么可以操作的空间（也可能是我见的太少了）。不过这里我们可以换一个角度来看这个式子
把式子一个一个写开
如果我们令,显然答案也可以表示成
这样就成果转化了需要求的东西。
但是这还不够，在我们赋予si实际意义之前，求它跟求pi之和没什么区别
不难发现，si表示在第i次，第i+1次，...第n次结束的概率之和，这其实也就等于第i-1次无法结束的概率（这个应该不难想）
所以我们求si，其实也就是求第i-1次不会结束的概率
接着转化题意：
现在有n个小球，要求选择i-1个小球，两两之间有至少k-1个小球
不妨先将i-1个小球摆好，这样整个集合被分成了i个位置，我们还有n-(i-1)个小球可以放进去
中间的i-2个位置每一个至少要有k-1个小球，所以我们先放进去(k-1)*(i-2)个小球，还剩下
n-(i-1)-(k-1)(i-2)个小球，这些相同的小球要放进i个位置里，可以有位置为空，所以直接隔板法即可
那么最后的方案数就是,再除以放i-1个小球的总方案数，
code
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\\n'
const ll N=4e5+10;
const ll mod=1e9+7;
ll n,m,x,y,k;
ll p[N],pp[N];
ll ksm(ll x,ll y)
{ll ans=1;while(y){if(y&1) ans=ans*x%mod;x=x*x%mod;y>>=1;}return ans;
}
ll inv(ll x)
{return ksm(x,mod-2);
}
void init()
{p[0]=1;for(int i=1;i<=400000;++i) p[i]=p[i-1]*i%mod;pp[400000]=inv(p[400000]);for(int i=400000-1;i>=0;--i) pp[i]=pp[i+1]*(i+1)%mod;
}
ll C(ll n,ll m)
{if(n<m) return 0;return p[n]*pp[m]%mod*pp[n-m]%mod;
}
void solve()
{init();cin>>n>>k;ll ans=0;for(int i=1;i<=n;++i){ans=(ans+C(n-(i-2)*(k-1),i-1)*inv(C(n,i-1))%mod)%mod; }cout<<ans<<endl;
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);ll t;cin>>t;while(t--)solve();return 0;
}
