題目鏈接：點擊查看

題目大意：給出 $n$ 個初始時熄滅的燈泡，每次操作會等概率打開一個燈泡，當每 $k$ 個連續的燈泡中出現了大于一個亮著的燈泡時停止操作，問期望操作次數是多少

題目分析：組合數學題留給隊友補了，只是想解釋一下這個模型，轉換的過程借用洛谷大牛的題解了（侵權刪）
主要是想講一下最后這個 “經典模型” ，其中 $P_i$ 為操作 $i$ 次后，還沒有結束的方案數。可以這樣考慮，因為任意兩個燈泡之間需要間隔為 $k$，所以放 $i$ 個燈泡兩兩之間需要有 $i?1$ 個隔板隔開，而每個隔板需要用 $k?1$ 個燈泡去充當，這樣對于剩下的 $n?(i?1)?(k?1)$ 個燈泡而言就可以隨便選 $i$ 個了，然后再用 $i?1$ 個隔板將其隔開就一定合法了

這也就對應著前半段的 $C_{n?(i?1)?(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(组合数学+推公式)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。