Submission #19936

#TimeUsernameProblemLanguageResultExecution timeMemory
19936ainta능력 (kriii4_S)C++98
10 / 100
2000 ms393428 KiB
#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]%Mod*D[i-1][j]%Mod*j%Mod + BS*D[i-1][j+1]%Mod*(i-j-1)%Mod + Succ[i]*C[i]%Mod*P[i-1][j])%Mod;
            D[i][j+1] = D[i][j+1]*Inv[i]%Mod;
        }
    }
    SS = 0;
    for(i=1;i<=n;i++)SS = (SS+D[n][i])%Mod;
    printf("%lld\n",SS*Pow(Invv(BS),n)%Mod);
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...