Submission #20107

#	Time	Username	Problem	Language	Result	Execution time	Memory
20107		fredldh	능력 (kriii4_S)	C++98	100 / 100	377 ms	392020 KiB

S

#include<stdio.h>
#define N 5000
#define M 1000000007
//#define mod(a) ((a)%M)
typedef long long int lld;
lld mod(lld a) {
    while(a < 0) a += M;
    return a % M;
}
lld pow(lld a, lld x) {
    if(!x) return 1;
    lld P = pow(a, x/2);
    if(x&1) return mod(a*mod(P*P));
    return mod(P*P);
}
lld inv(lld a) {
    return pow(a, M-2);
}
lld div(lld a, lld b) {
    return mod(a*inv(b));
}
int n;
lld fac[N+1];
lld p[N+1], d[N+1], np[N+1];
lld f1[N+1][N+1], f2[N+1][N+1];
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; ++i) {
        scanf("%lld%lld", &p[i], &d[i]);
        np[i] = div(pow(10,9)-p[i], pow(10,9));
        p[i] = div(p[i], pow(10,9));
    }
    fac[0] = 1;
    for(int i = 1; i <= n; ++i) fac[i] = mod(fac[i-1]*i);

    for(int i = 1; i <= n; ++i) {
        f1[i][1] = mod(f1[i-1][1] + np[i]);
        f2[i][1] = mod(f2[i-1][1] + mod(p[i]*d[i]));
        for(int j = 2; j <= i; ++j) {
            f1[i][j] = mod(f1[i-1][j] + mod(f1[i-1][j-1]*mod(j*np[i])));
            f2[i][j] = mod(f2[i-1][j] + mod(mod(f1[i-1][j-1]*mod(p[i]*d[i])) + mod(f2[i-1][j-1]*mod((j-1)*np[i]))));
        }
    }

    lld res = 0;
    for(int i = 1; i <= n; ++i) {
        res = mod(res + div(mod(f2[n][i]*fac[n-i]), fac[n]));
    }
    printf("%lld\n", res);
    return 0;
}

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