CodeForces - 1523E Crypto Lights(组合数学+推公式)

题目链接：点击查看

题目大意：给出 $n$ 个初始时熄灭的灯泡，每次操作会等概率打开一个灯泡，当每 $k$ 个连续的灯泡中出现了大于一个亮着的灯泡时停止操作，问期望操作次数是多少

题目分析：组合数学题留给队友补了，只是想解释一下这个模型，转换的过程借用洛谷大牛的题解了（侵权删）
主要是想讲一下最后这个 “经典模型” ，其中 $P_i$ 为操作 $i$ 次后，还没有结束的方案数。可以这样考虑，因为任意两个灯泡之间需要间隔为 $k$，所以放 $i$ 个灯泡两两之间需要有 $i-1$ 个隔板隔开，而每个隔板需要用 $k-1$ 个灯泡去充当，这样对于剩下的 $n-(i-1)\ast (k-1)$ 个灯泡而言就可以随便选 $i$ 个了，然后再用 $i-1$ 个隔板将其隔开就一定合法了

这也就对应着前半段的 $C_{n-(i-1)\ast (k-1)}^i$ 了

对于后半段的贡献可以这样考虑，假如从一开始 $n$ 个灯泡开始选 $i$ 个，依次选中的概率分别是 $\{\frac{1}{n},\frac{1}{n-1},\frac{1}{n-2},...,\frac{1}{n-i+1}\}$，累乘起来就是 $\frac{(n-i)!}{n!}$，又因为选择 $i$ 个灯泡的次序可以随意，所以还需要乘以 $i!$，所以后半段的贡献就是 $\frac{i!(n-i)!}{n!}$ 了

对于本题需要注意的是，如果将 $P_i$ 的 $i=0$ 代入，整个式子是 $1$，也就是答案初始化的数值了

代码：

// Problem: E. Crypto Lights // Contest: Codeforces - Deltix Round, Spring 2021 (open for everyone, rated, Div. 1 + Div. 2) // URL: https://codeforces.com/contest/1523/problem/E // Memory Limit: 256 MB // Time Limit: 3000 ms // // Powered by CP Editor (https://cpeditor.org)// #pragma GCC optimize(2) // #pragma GCC optimize("Ofast","inline","-ffast-math") // #pragma GCC target("avx,sse2,sse3,sse4,mmx") #include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cmath> #include<cstring> #include<algorithm> #include<stack> #include<climits> #include<queue> #include<map> #include<set> #include<sstream> #include<cassert> #include<bitset> #include<list> #include<unordered_map> #define lowbit(x) x&-x using namespace std; typedef long long LL; typedef unsigned long long ull; template<typename T> inline void read(T &x) {T f=1;x=0;char ch=getchar();while(0==isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}while(0!=isdigit(ch)) x=(x<<1)+(x<<3)+ch-'0',ch=getchar();x*=f; } template<typename T> inline void write(T x) {if(x<0){x=~(x-1);putchar('-');}if(x>9)write(x/10);putchar(x%10+'0'); } const int inf=0x3f3f3f3f; const int N=1e6+100; const int mod=1e9+7; LL fac[N],inv[N]; LL q_pow(LL a,LL b) {LL ans=1;while(b) {if(b&1) {ans=ans*a%mod;}a=a*a%mod;b>>=1;}return ans; } void init() {fac[0]=1;for(int i=1;i<N;i++) {fac[i]=fac[i-1]*i%mod;}inv[N-1]=q_pow(fac[N-1],mod-2);for(int i=N-2;i>=0;i--) {inv[i]=inv[i+1]*(i+1)%mod;} } LL C(int n,int m) {return fac[n]*inv[m]%mod*inv[n-m]%mod; } int main() { #ifndef ONLINE_JUDGE // freopen("data.in.txt","r",stdin); // freopen("data.out.txt","w",stdout); #endif // ios::sync_with_stdio(false);init();int w;cin>>w;while(w--) {int n,k;read(n),read(k);LL ans=1;for(int i=1;n-(i-1)*(k-1)>=i;i++) {ans=(ans+C(n-(i-1)*(k-1),i)*q_pow(C(n,i),mod-2))%mod;}cout<<ans<<endl;}return 0; } 超强干货来袭 云风专访：近40年码龄，通宵达旦的技术人生

总结

以上是生活随笔为你收集整理的CodeForces - 1523E Crypto Lights(组合数学+推公式)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。