根据期望的线性性质，考虑求出做出第 $i$ 题的概率 $p_i$ ，答案可以转化为：
$$
ans=\sum_{i=1}^np_i
$$
考虑 $p_i$ 的求法，对于每个题目 $i$，枚举它前面（包括 $i$）有 $j$ 题目多用了一秒，所以：
$$
p_i=\frac{1}{2^i}\sum_{j=0}^{T-s_i}C_i^j
$$
那后面的这个 $\sum_{j=0}^{T-s_i}C_i^j$ 又咋求？
定义 $S(n,m)$ 表示在 $n$ 个物品中选至多 $m$ 个的方案数，也就是 $\sum_{i=0}^{m}C_n^i$
这个 $S(n,m)$ 有递推式：
$$
S(n,m)=S(n-1,m)+S(n-1,m-1)
$$
理解方式和组合数的差不多，即考虑第 $n$ 个物品选不选：
- 若不选，则在前 $n-1$ 个物品中最多选 $m$ 个。
- 若选，在前 $n-1$ 个物品中最多选 $m-1$ 个
但是用这个递推式是只能做到 $n^2$ 的。
我们可以通过 $S$ 的定义得到：
$$
S(n,m-1)=S(n,m)-C_n^m\\
$$
所以：
$$
\begin{aligned}
S(n,m)=&S(n-1,m)+S(n-1,m-1)\\
=&S(n-1,m)+S(n-1,m)-C_{n-1}^{m}\\
=&2S(n-1,m)-C_{n-1}^{m}\\
\end{aligned}
$$
所以：
$$
S(n+1,m)=2S(n,m)-C_n^m
$$
这样，我们就可以 $O(1)$ 地通过 $S(n,m)$ 求出 $S(n,m-1)$ 和 $S(n+1,m)$ 了。
观察我们 $p_i$ 求法：
$$
p_i=\frac{1}{2^i}\times S(i,T-s_i)
$$
注意到这里 $T-s_i$ 是随着 $i$ 的递增而递减的，所以可以用类似双指针的方式做到 $O(n)$ 求出所有 $p_i$ 的值。
代码：（丑的一匹）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
|
#include <bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
using namespace std;
const int N=2e5+10,mod=1e9+7;
int n;ll T,t[N],s[N],inv[N],fac[N],p[N];
ll qpow(ll x,ll y){
ll ans=1;
while(y){
if(y&1) ans=ans*x%mod;
x=x*x%mod,y>>=1;
}
return ans;
}
void init(){
fac[0]=1;
for(int i=1;i<=n;i++) fac[i]=fac[i-1]*i%mod;
inv[n]=qpow(fac[n],mod-2);
for(int i=n-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
}
ll C(int n,int m){
if(m>n) return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int nwn,nwm;
ll nws;
ll S(int n,int m){
while(nwn<n) nws=(2*nws%mod-C(nwn,nwm))%mod,nwn++;
while(nwm>m) nws=(nws-C(nwn,nwm))%mod,nwm--;
return nws;
}
int main(){
cin>>n>>T;init();
for(int i=1;i<=n;i++) cin>>t[i],s[i]=s[i-1]+t[i];
nwn=1,nwm=min((ll)n,T-s[1]);
for(int i=0;i<=nwm;i++) (nws+=C(nwn,i))%=mod;
if(s[1]>T) {cout<<0;return 0;}
ll pwinv=500000004,ans=0;
ans=p[1]=(nws*pwinv)%mod;
for(int i=2;i<=n;i++){
if(s[i]>T) break;
(pwinv*=500000004)%=mod;
p[i]=S(i,min((ll)n,T-s[i]))*pwinv%mod;
(ans+=p[i])%=mod;
}
cout<<(ans+mod)%mod;
return 0;
}
|