「CF1194F」Crossword Expert

发表于

题目链接：https://codeforces.com/problemset/problem/1194/F。

假设能恰好搞出$k$个的概率是$p_k$，那么答案就是$\sum kp_k$。

有一个很经典的套路，就是说如果你把概率做后缀和，设成$p_k$表示搞出至少$k$个的概率，答案就是$\sum p_k$，这时候$p_k$就会好算一些。

可以直接把式子写出来了：

$s_k$是前缀和。

那么现在就是要算$f_{n,m}=\sum _{i=0}^{n}\binom{m}{i}$。

注意到我们要算的$f$第一维递减，而第二维递增，并且两维都是$O(n)$（因为第一维如果过大可以直接整成$n$，显然答案不变）。

首先明显$f$可以$O(1)$的让第一维减一：$f_{n,m}=f_{n+1,m}-\binom{m}{n+1}$。

第二维也比较简单，把组合数的递推式套进去就行了：

所以复杂度$O(n)$。

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include<bits/stdc++.h>
using namespace std;
 
#define int long long 
 
void read(int &x) {
    x=0;int f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-f;
    for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';x*=f;
}
 
void print(int x) {
    if(x<0) putchar('-'),x=-x;
    if(!x) return ;print(x/10),putchar(x%10+48);
}
void write(int x) {if(!x) putchar('0');else print(x);putchar('\n');}
 
#define lf double
#define ll long long 
 
#define pii pair<int,int >
#define vec vector<int >
 
#define pb push_back
#define mp make_pair
#define fr first
#define sc second
 
#define data asd09123jdf02i3h
 
#define FOR(i,l,r) for(int i=l,i##_r=r;i<=i##_r;i++)
 
const int maxn = 1e6+10;
const int inf = 1e9;
const lf eps = 1e-8;
const int mod = 1e9+7;
const int inv2 = 5e8+4;
 
int s[maxn],n,T,fac[maxn],ifac[maxn],inv[maxn];
 
void gen() {
    inv[0]=inv[1]=fac[0]=ifac[0]=1;
    for(int i=1;i<=n;i++) {
        if(i>1) inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;
        fac[i]=1ll*fac[i-1]*i%mod;
        ifac[i]=1ll*ifac[i-1]*inv[i]%mod;
    }
}
 
int c(int a,int b) {
    if(a<b||b<0) return 0;
    return 1ll*fac[a]*ifac[b]%mod*ifac[a-b]%mod;
}
 
signed main() {
    read(n),read(T);gen();
    for(int i=1,x;i<=n;i++) read(x),s[i]=s[i-1]+x;
    int a=min(T-s[1],n),b=1,ans=0,res=0,iv=inv2;
    for(int i=0;i<=a;i++) res=(res+c(b,i))%mod;ans=(ans+1ll*iv*res%mod)%mod;
    for(int i=2;i<=n;i++) {
        while(a>T-s[i]&&a>=0) res=(res-c(b,a)+mod)%mod,a--;
        res=(2ll*res%mod-c(b,a)+mod)%mod;b++;
        iv=1ll*iv*inv2%mod;
        ans=(ans+1ll*iv*res%mod)%mod;
    }write(ans);
    return 0;
}