oj.uz

답안 #19938

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
19938 2016-02-25T07:28:54 Z ainta 능력 (kriii4_S) C++
10 / 100
 2000 ms 1396 KB 
#include<stdio.h>
long long BS = 1000000000, Mod = 1000000007;
int n, pv;
long long P[2][5010], D[2][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;
    pv = 0;
    for(i=1;i<=n;i++){
        P[!pv][0]=P[pv][0]*BS%Mod;
        for(j=1;j<=i;j++){
            P[!pv][j] = (P[pv][j]*(i-j)%Mod*Inv[i]%Mod*BS%Mod + P[pv][j-1]*j%Mod*Inv[i]%Mod*Fail[i]%Mod)%Mod;
        }
        for(j=0;j<i;j++){
            D[!pv][j+1] = (Fail[i]%Mod*D[pv][j]%Mod*j%Mod + BS*D[pv][j+1]%Mod*(i-j-1)%Mod + Succ[i]*C[i]%Mod*P[pv][j])%Mod;
            D[!pv][j+1] = D[!pv][j+1]*Inv[i]%Mod;
        }
        pv = !pv;
    }
    SS = 0;
    for(i=1;i<=n;i++)SS = (SS+D[pv][i])%Mod;
    printf("%lld\n",SS*Pow(Invv(BS),n)%Mod);
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 1396 KB Output is correct
2 Correct 5 ms 1396 KB Output is correct
3 Correct 5 ms 1396 KB Output is correct
4 Correct 5 ms 1396 KB Output is correct
5 Correct 5 ms 1396 KB Output is correct
6 Correct 5 ms 1396 KB Output is correct
7 Correct 5 ms 1396 KB Output is correct
8 Correct 5 ms 1396 KB Output is correct
9 Correct 5 ms 1396 KB Output is correct
10 Correct 5 ms 1396 KB Output is correct
11 Correct 5 ms 1396 KB Output is correct
12 Correct 5 ms 1396 KB Output is correct
13 Correct 5 ms 1396 KB Output is correct
14 Correct 5 ms 1396 KB Output is correct
15 Correct 5 ms 1396 KB Output is correct
16 Correct 4 ms 1396 KB Output is correct
17 Correct 4 ms 1396 KB Output is correct
18 Correct 4 ms 1396 KB Output is correct
19 Correct 5 ms 1396 KB Output is correct
20 Correct 3 ms 1396 KB Output is correct

Subtask #2
0.0 / 90.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 2000 ms 1396 KB Program timed out
2 Halted 0 ms 0 KB -