제출 #19936

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
19936		ainta	능력 (kriii4_S)	C++98	10 / 100	2000 ms	393428 KiB

S

#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);
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 90