oj.uz

Submission #19932

# Submission time Handle Problem Language Result Execution time Memory
19932 2016-02-25T07:23:35 Z ainta 능력 (kriii4_S) C++
10 / 100
 2000 ms 393428 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], Inv[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 Invv(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];
        Inv[i] = Invv(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(Invv(BS),n)%Mod);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 393428 KB Output is correct
2 Correct 7 ms 393428 KB Output is correct
3 Correct 3 ms 393428 KB Output is correct
4 Correct 3 ms 393428 KB Output is correct
5 Correct 3 ms 393428 KB Output is correct
6 Correct 3 ms 393428 KB Output is correct
7 Correct 3 ms 393428 KB Output is correct
8 Correct 7 ms 393428 KB Output is correct
9 Correct 0 ms 393428 KB Output is correct
10 Correct 7 ms 393428 KB Output is correct
11 Correct 3 ms 393428 KB Output is correct
12 Correct 3 ms 393428 KB Output is correct
13 Correct 3 ms 393428 KB Output is correct
14 Correct 3 ms 393428 KB Output is correct
15 Correct 3 ms 393428 KB Output is correct
16 Correct 5 ms 393428 KB Output is correct
17 Correct 6 ms 393428 KB Output is correct
18 Correct 0 ms 393428 KB Output is correct
19 Correct 7 ms 393428 KB Output is correct
20 Correct 5 ms 393428 KB Output is correct

Subtask #2
0.0 / 90.0

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