当前位置：首页 > article >正文

另类推柿子 Crypto Lights

article 2024/11/18 2:39:00

Crypto Lights

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

思路：

没见过这样子的推柿子的题，也算是开开眼了

考虑一个非常正确的答案

$ans=\sum_{i=1}^{n} i*p_i$ ,其中pi表示第i次结束的概率，

显然这就是期望的定义求法。但是这样一个式子在大多数时候并不能带给我我们实质性的进展，因为它没有什么可以操作的空间（也可能是我见的太少了）。不过这里我们可以换一个角度来看这个式子

把式子一个一个写开

$p_1+2p_2+3p_3+....+np_n$

$=(p1+p2+p3+...+pn)+(p2+p3+...+pn)+...+(p_{n-1}+p_n)+p_n$

如果我们令 $s_i=\sum_{j=i}^{n} p_i$ ,显然答案也可以表示成 $\sum s_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个位置里，可以有位置为空，所以直接隔板法即可

那么最后的方案数就是 $\binom{n-(i-1)-(k-1)(i-2)+(i-1)}{i-1}=\binom{n-(k-1)(i-2)}{i-1}$ ,再除以放i-1个小球的总方案数， $s_i=\frac{\binom{n-(k-1)(i-2)}{i-1}}{\binom{n}{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;
}

查看全文

http://www.kler.cn/a/7262.html