oj.uz

Submission #19930

# Submission time Handle Problem Language Result Execution time Memory
19930 2016-02-25T07:22:06 Z ainta 능력 (kriii4_S) C++
10 / 100
 2000 ms 393388 KB 
#include<stdio.h>
long long BS = 1000000000, Mod = 1000000007;
int n;
long long P[5010][5010], D[5010][5010], C[5010], Succ[5010], Fail[5010];
long long Pow(long long a, long long b){
    long long r = 1;
    while(b){
        if(b%2)r=r*a%Mod;
        a=a*a%Mod;b/=2;
    }
    return r;
}
long long Inv(long long a){
    return Pow(a,Mod-2);
}
int main(){
    int i, j;
    scanf("%d",&n);
    for(i=1;i<=n;i++){
        scanf("%lld %lld",&Succ[i],&C[i]);
        Fail[i] = BS-Succ[i];
    }
    P[0][0]=1;
    long long SS;
    for(i=1;i<=n;i++){
        P[i][0]=P[i-1][0]*BS%Mod;
        for(j=1;j<=i;j++){
            P[i][j] = (P[i-1][j]*(i-j)%Mod*Inv(i)%Mod*BS%Mod + P[i-1][j-1]*j%Mod*Inv(i)%Mod*Fail[i]%Mod)%Mod;
        }
        for(j=0;j<i;j++){
            D[i][j+1] = (Fail[i]*Inv(i)%Mod*D[i-1][j]%Mod*j%Mod + BS*D[i-1][j+1]%Mod*(i-j-1)%Mod*Inv(i))%Mod;
            D[i][j+1] = (D[i][j+1] + Succ[i]*Inv(i)%Mod*C[i]%Mod*P[i-1][j])%Mod;
        }
    }
    SS = 0;
    for(i=1;i<=n;i++)SS = (SS+D[n][i])%Mod;
    printf("%lld\n",SS*Pow(Inv(BS),n)%Mod);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 88 ms 393388 KB Output is correct
2 Correct 86 ms 393388 KB Output is correct
3 Correct 82 ms 393388 KB Output is correct
4 Correct 86 ms 393388 KB Output is correct
5 Correct 80 ms 393388 KB Output is correct
6 Correct 81 ms 393388 KB Output is correct
7 Correct 76 ms 393388 KB Output is correct
8 Correct 88 ms 393388 KB Output is correct
9 Correct 79 ms 393388 KB Output is correct
10 Correct 85 ms 393388 KB Output is correct
11 Correct 82 ms 393388 KB Output is correct
12 Correct 76 ms 393388 KB Output is correct
13 Correct 80 ms 393388 KB Output is correct
14 Correct 83 ms 393388 KB Output is correct
15 Correct 88 ms 393388 KB Output is correct
16 Correct 61 ms 393388 KB Output is correct
17 Correct 70 ms 393388 KB Output is correct
18 Correct 68 ms 393388 KB Output is correct
19 Correct 85 ms 393388 KB Output is correct
20 Correct 63 ms 393388 KB Output is correct

Subtask #2
0.0 / 90.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2000 ms 393384 KB Program timed out
2 Halted 0 ms 0 KB -