CF1523E Crypto Lights 题解

· · 题解

考虑计算答案。采用另一篇题解的解法使用期望的定义与性质辅助考虑。那篇题解对我也很大启发帮助。

显然期望等于概率乘权值之和。定义 p_i 为点亮 i 颗灯结束操作的概率。那么显然有期望：

E = \sum_{i=1}^{n} p_i i

注意到这个 i，那么对 p 做一个后缀和，即令 s_i = \sum_{j=i}^n p_i。那么有：

E = \sum_{i=1}^n s_i

考虑构造这样的一个互不影响的部分，并使得意义和定义能够对应 E 和 s_i。有一个比较显然的思路是 s_i 的意义是点亮 i-1 颗灯还是没结束的概率。

思考到这里的原因是，我们只有保证第 i-1 颗灯点亮还是无法结束，才能保证点亮 i 一直到 n 颗的某一颗时结束。

于是对应完成，考虑计算 s_i。注意到 s_i 的定义是，点亮了 i-1 颗灯还是无法结束的概率。

考虑采用组合定义。显然一共有 \dbinom{n}{i-1} 种选法。合法的选法应该先排除距离之间的影响。我们假设已经选好了点亮的灯泡的位置，剩下的我们只需要在点亮的两颗灯泡里面插入 k-1 个不亮的灯泡就行了。

这样的话一共有 n-(k-1)\times(i-2) 个合法的位置，选择 i-1 个，即共有 \dbinom{n-(k-1)\times(i-2)}{i-1}，得到：

s_i = \dfrac{\dbinom{n-(k-1)\times(i-2)}{i-1}}{\dbinom{n}{i-1}}

计算即可。注意特判 i=0 的时候 s_i 为 1。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL MOD=1e9+7;
LL fac[100005],ifac[100005];
LL QuickPow(LL x,LL p)
{
    LL ans=1,base=x;
    while(p)
    {
        if(p&1) ans=(ans*base)%MOD;
        base=(base*base)%MOD;
        p>>=1;
    }
    return ans;
}
LL C(LL n,LL m){if(n<m) return 0;return fac[n]*ifac[m]%MOD*ifac[n-m]%MOD;}
int main(){
    fac[0]=1;
    for(LL i=1;i<=100000;++i)   fac[i]=fac[i-1]*i%MOD;
    ifac[100000]=QuickPow(fac[100000],MOD-2);
    for(LL i=99999;~i;--i)  ifac[i]=ifac[i+1]*(i+1)%MOD;
    LL T;
    scanf("%lld",&T);
    while(T-->0)
    {
        LL n,k;
        scanf("%lld %lld",&n,&k);
        LL ans=1;
        for(LL i=1;i<n;++i) (ans+=C(n-(i-1)*(k-1),i)*QuickPow(C(n,i),MOD-2))%=MOD;
        printf("%lld\n",ans);
    }
    return 0;
}