[CF1523E]Crypto Lights

本文主要是介绍[CF1523E]Crypto Lights，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Crypto Lights

题目大意

给你一个长度为 $n$ 的 $0 / 1$ 序列，最开始全都为 $0$ 。你将一直执行下列操作：

从为 $0$ 的点中等概率选择一个点，将其变为 $1$ 。
如果有两个为 $1$ 的点之间距离小于 $k$ ，则停止操作，否则继续执行上面的操作。

请问你执行停止后序列中 $1$ 的期望个数。 $(2\leqslant k\leqslant n\leqslant 10^5)$

题解

~~先吐槽一下这题意真的很难懂，我读错了 $3$ 次。~~

法一

我们可以发现 $E(Number\,of\,1's\,occurrences)=E(times\,while\,stop)=E(times\, before\,stop)+1$ 。
我们可以去寻找在停止之前操作了多少次。

假设我们已经操作了 $p$ 次，那么我们现在有 $p$ 个 $1$ ，而每两个 $1$ 之间至少有 $k - 1$ 个 $0$ ，总共有 $(p - 1) (k - 1)$ 个 $0$ 。
我们将这 $(p - 1) (k - 1)$ 个 $0$ 去掉，我们之后相当于从剩 $n - (p - 1) (k - 1)$ 个位置中选择 $k$ 个为 $1$ ，再将那 $(p - 1) (k - 1)$ 个 $0$ 插入两个不同位置的 $1$ 中间的空隙中。可以发现，这样与合法的方案是一一对应的。
于是，我们选择 $p$ 个数时未停止的方案数为 $\binom{n-(p-1)(k-1)}{p}p!$ ，而每种方案的概率为 $\frac{(n-i)!}{n!}$ 。

所以我们的期望的操作次数为 $\sum_{i=1}^{n}\frac{\binom{n-(i-1)(k-1)}{i}i!(n-i)!}{n!}$ 。
加上 $1$ 就是最后的答案。

法二

或者我们可以直接考虑在什么时候停止，还是可以用上面的方法退出选择 $i$ 个数时未停止的方案数为 $\binom{n-(i-1)(k-1)}{i}i!$ ，记作 $g_{i}$ 。
那么选择 $i$ 个时已停止的方案数为 $n-i+1)dp_{i-1}-dp_{i}$ 。
答案为 $\sum_{i=1}^{n}((n-i+1)dp_{i-1}-dp_{i})\frac{(n-i)!}{n!}$

其实两种做法本质上是一样的。

时间复杂度都是 $O\left(n\right)$ 。

源码

法一

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define lowbit(x) (x&-x)
#define reg register
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int mo=1e9+7;
const int zero=500;
const LL jzm=2333;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
typedef pair<int,int> pii;
const double PI=acos(-1.0);
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int add(int x,int y){return x+y<mo?x+y:x+y-mo;}
int t,n,k,pow2[MAXN],fac[MAXN],f[MAXN],inv[MAXN],ans;
int qkpow(int a,int s){int t=1;while(s){if(s&1)t=1ll*a*t%mo;a=1ll*a*a%mo;s>>=1;}return t;}
void init(){pow2[0]=1;for(int i=1;i<=1e5;i++)pow2[i]=2ll*pow2[i-1]%mo;fac[0]=fac[1]=f[1]=inv[0]=inv[1]=1;for(int i=2;i<=1e5;i++)fac[i]=1ll*i*fac[i-1]%mo,f[i]=1ll*(mo-mo/i)*f[mo%i]%mo,inv[i]=1ll*inv[i-1]*f[i]%mo;
}
int C(int x,int y){if(x<y||x<0||y<0)return 0;return 1ll*fac[x]*inv[y]%mo*inv[x-y]%mo;
}
signed main(){read(t);init();while(t--){read(n);read(k);ans=0;for(int i=1;i<=n&&(i-1)*(k-1)<=n;i++)ans=add(ans,1ll*C(n-(i-1)*(k-1),i)*fac[i]%mo*inv[n]%mo*fac[n-i]%mo);printf("%d\n",add(ans,1));}return 0;
}

法二

#include<bits/stdc++.h>
using namespace std;
#define MAXN 200005
#define lowbit(x) (x&-x)
#define reg register
#define mkpr make_pair
#define fir first
#define sec second
typedef long long LL;
typedef unsigned long long uLL;
const LL INF=0x3f3f3f3f3f3f3f3f;
const int mo=1e9+7;
const int zero=500;
const LL jzm=2333;
const int orG=3,invG=332748118;
const double Pi=acos(-1.0);
typedef pair<int,int> pii;
const double PI=acos(-1.0);
template<typename _T>
_T Fabs(_T x){return x<0?-x:x;}
template<typename _T>
void read(_T &x){_T f=1;x=0;char s=getchar();while(s>'9'||s<'0'){if(s=='-')f=-1;s=getchar();}while('0'<=s&&s<='9'){x=(x<<3)+(x<<1)+(s^48);s=getchar();}x*=f;
}
template<typename _T>
void print(_T x){if(x<0){x=(~x)+1;putchar('-');}if(x>9)print(x/10);putchar(x%10+'0');}
int add(int x,int y){return x+y<mo?x+y:x+y-mo;}
int t,n,k,pow2[MAXN],fac[MAXN],f[MAXN],inv[MAXN],ans,dp[MAXN],sum;
int qkpow(int a,int s){int t=1;while(s){if(s&1)t=1ll*a*t%mo;a=1ll*a*a%mo;s>>=1;}return t;}
void init(){pow2[0]=1;for(int i=1;i<=1e5;i++)pow2[i]=2ll*pow2[i-1]%mo;fac[0]=fac[1]=f[1]=inv[0]=inv[1]=1;for(int i=2;i<=1e5;i++)fac[i]=1ll*i*fac[i-1]%mo,f[i]=1ll*(mo-mo/i)*f[mo%i]%mo,inv[i]=1ll*inv[i-1]*f[i]%mo;
}
int C(LL x,int y){if(x<y||x<0||y<0)return 0;return 1ll*fac[x]*inv[y]%mo*inv[x-y]%mo;
}
signed main(){read(t);init();while(t--){read(n);read(k);ans=sum=0;dp[0]=1;for(int i=1;i<=n;i++){dp[i]=1ll*C(1ll*n-1ll*(i-1)*(k-1),i)*fac[i]%mo;int tmp=add(mo-dp[i],1ll*(n-i+1)*dp[i-1]%mo);ans=add(ans,1ll*i*tmp%mo*fac[n-i]%mo*inv[n]%mo);}printf("%d\n",ans);}return 0;
}