Submission #19939

#	Time	Username	Problem	Language	Result	Execution time	Memory
19939		ainta	능력 (kriii4_S)	C++98	100 / 100	1916 ms	1396 KiB

S

#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 + P[pv][j-1]*j%Mod*Inv[i]%Mod*Fail[i])%Mod;
        }
        for(j=0;j<i;j++){
            D[!pv][j+1] = (Fail[i]%Mod*D[pv][j]%Mod*j + BS*D[pv][j+1]%Mod*(i-j-1) + 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 / 10
• Subtask 2: 90 / 90