CF1194F Crossword Expert

发表于 | 阅读数

题面很长，但是题意很简单(读了半天屈服于百度翻译)

题意:

李华同学有$n$道题，每道题需要$t[i]$时间，但是李华会失手1/2概率会花费$t[i]+1$的时间
问在T时间内做出题数的期望E
先看第一个样例
3 5
2 2 2
做一道题 $\frac{1}{2}$ 3分钟 $\frac{1}{2}$ 2分钟
做二道题 $\frac{1}{4}$ 4分钟 $\frac{1}{4}$ 5分钟 $\frac{1}{4}$ 5分钟 $\frac{1}{4}$ 6分钟
所以
需要将每末尾的时间进行判断$n$太大就很烦
考虑分别算概率

将罚时随机分配给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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <cmath>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 2e5+10;
const int mod = 1e9+7;
 
int addmod(int x, int y)
{
    if (y < 0) x += y;
    else x = x - mod + y;
    if (x < 0) x += mod;
    return x;
}
 
int qpow(int a,int b,int mo)
{
    int res=1;
    while(b)
    {
        if(b&1)
            res=1ll*res*a%mo;
        a=1ll*a*a%mo;
        b>>=1;
    }
    return res;
}
int invfac2[N],invfac[N],fac[N];
void init()
{
    fac[0]=1;
    for(int i=1;i<N;i++)
        fac[i]=1ll*fac[i-1]*i%mod;
    invfac[N-1]=qpow(fac[N-1],mod-2,mod);
    invfac[0]=1;
    for(int i=N-2;i>=1;i--)
        invfac[i]=1ll*invfac[i+1]*(i+1)%mod;
    invfac2[1]=qpow(2,mod-2,mod);
    for(int i=2;i<N;i++)
        invfac2[i]=1ll*invfac2[i-1]*invfac2[1]%mod;    
}
int Calc(int n,int m)
{
    if(n>m)
        return 0;
    else
        return 1ll*fac[m]*invfac[n]%mod*invfac[m-n]%mod;
}
int n,ans;
ll T,t[N];
bool Flag=0;
int main()
{
    init();
    scanf("%d%lld",&n,&T);
    for(int i=1;i<=n;i++)
        scanf("%lld",&t[i]);
    ll sum=0;
    int s=2;
    int r=n;
    for(int i=1;i<=n;i++)
    {
        sum+=t[i];
        if(T-sum>=i)
            ans=addmod(1,ans);
        else if(T-sum<0)
            break;
        else 
        {
 
            for(int j=T-sum+1;j<=r;j++)
                s=addmod(s,-Calc(j,i));
           // cout<<s<<" "<<i<<endl;
            ans=addmod(1ll*s*invfac2[i]%mod,ans);
            r=T-sum;
            Flag=1;
        }
        s=2ll*s%mod;;
        if(Flag)
            s=addmod(s,-Calc(r,i));
        //cout<<ans<<" "<<s<<endl;
    }
    printf("%d\n",ans);
}