题意：给定时间T,事件花费的时间数组a, 每件事有二分之一的几率多花费一秒钟, 求在给定时间内能晚场的事件个数的期望

题面

Strategy: 先看大佬的博客,这题有两个难点, 首先是想到该期望应该等于$$\frac{1}{2^x}\sum _{i=0}^{i\le maxdo}{C}_x^i(前x件事中有i件要多花一秒钟\times 多花一秒钟的概率)$$.然后找到一个分界点X, 使得所有在X之前的事件即使每件事都多花一秒钟也全部做得完(即对答案贡献为1的事件),然后在考虑不一定能做得完的事件, 最后想到该怎样优化组合数前缀和

要想O(1)转移组合数前缀和, 要知道一下前置知识点

$C_n^k+C_n^{k+1}=C_{n+1}^{k+1}$ 于是聪明的你说不定会想到$$\sum _{i=0}^{k+1}{C}_{n+1}^i=C_n^{k+1}+2\times \sum _{i=0}^k{C}_n^i$$

于是就有以下产物

#include <bits/stdc++.h> #include <bits/extc++.h> #define oo INT_MAX #define ll long long #define db double #define all(a) a.begin(), a.end() #define met(a, b) memset(a, b, sizeof(a)) #define _rep(i, a, b) for (int i = (a); i <= (b); ++i) #define _rev(i, a, b) for (int i = (a); i >= (b); --i) #define _for(i, a, b) for (int i = (a); i < (b); ++i) #define lowbit(x) x &(-x) #define pi acos(-1.0) using namespace std; using namespace __gnu_pbds; const int maxn = 2e5 + 10, mod = 1e9 + 7; ll T, n, sumt[maxn], inv[maxn], fac[maxn], t[maxn], invf[maxn]; void cala_inv() //逆元相关 { invf[0] = invf[1] = fac[1] = fac[0] = 1; inv[1] = 1; _for(i, 2, maxn) fac[i] = fac[i - 1] * i % mod, inv[i] = 1ll * (mod - mod / i) * inv[mod % i] % mod, invf[i] = invf[i - 1] * inv[i] % mod; } ll C(ll m, ll n) { if (n < m) return 0; return (fac[n] * invf[n - m] % mod) * invf[m] % mod; } ll curC = 0, dx1; ll calc_SigmaC(int cur) { dx1 = min(1ll * cur, T - sumt[cur]); _rep(i, 0, dx1) { curC = (curC + C(i, cur)) % mod; } return curC; } ll calc_nxt(int cur) { ll dx2 = min(1ll * cur, T - sumt[cur]); ll tmpC = ((curC * 2 % mod) + C(dx1 + 1, cur - 1)) % mod; while (dx1 >= dx2) { tmpC = (tmpC - C(dx1-- + 1, cur) + mod) % mod; } dx1++; // curC = tmpC, dx1 = dx2; return curC = tmpC; } int main() { ios::sync_with_stdio(0); cin >> n >> T; cala_inv(); _rep(i, 1, n) { cin >> t[i]; sumt[i] = sumt[i - 1] + t[i]; } ll ans = 0; int x = 1; ll inv2x = inv[2]; while(x <= n && sumt[x] + x <= T){ x ++; ans ++; inv2x = inv2x*inv[2] %mod; } if (x <= n) { calc_SigmaC(x); for (; x <= n; x++) { ans = (ans + curC * inv2x) % mod; if (T - sumt[x + 1] < 0) break; inv2x = (inv2x * inv[2]) % mod; curC = calc_nxt(x + 1); } } cout << ans << endl; }