Submission #21285

#	Time	Username	Problem	Language	Result	Execution time	Memory
21285		suzy	능력 (kriii4_S)	C++11	100 / 100	1533 ms	392052 KiB

S

#include <stdio.h>
#include <string.h>

typedef long long lli;

#define MOD 1000000007LL

lli p[5001], q[5001], d[5001], fac[5001];
int n;
lli r[5001][5001], rd[5001][5001];

lli pw(lli n, lli x) {
    if(x==0) return 1;
    if(x%2) return n*pw(n,x-1)%MOD;
    else { lli ret=pw(n,x/2); return ret*ret%MOD; }
}

int main() {
    memset(rd,-1,sizeof(rd));
    fac[0]=1;
    for(lli i=1;i<=5000;i++)
        fac[i]=fac[i-1]*i%MOD;
    scanf("%d",&n);
    for(int i=1;i<=n;i++) {
        scanf("%lld %lld",&p[i],&d[i]);
        q[i]=(1000000000-p[i])*pw(1000000000,MOD-2)%MOD;
        p[i]=p[i]*pw(1000000000,MOD-2)%MOD;
    }
    for(int i=0;i<=5000;i++) {
        r[0][i]=1;
    }
    for(int j=1;j<=n;j++) {
        for(int i=1;i<=n;i++)
            r[i][j]=(r[i-1][j-1]*q[j]%MOD+r[i][j-1])%MOD;
    }
    for(int i=0;i<=n;i++) {
        rd[0][i]=1;
    }
    for(int i=1;i<=n;i++) {
        for(int j=1;j<=n;j++) {
            rd[i][j]=(r[i][n]-rd[i-1][j]*q[j]%MOD+MOD)%MOD;
        }
    }
    lli res=0;
    for(int i=1;i<=n;i++) {
        lli mult=p[i]*d[i]%MOD, add=0;
        for(int j=0;j<=n-1;j++) {
            lli ff=fac[j]*fac[n-j-1]%MOD;
            add+=ff*rd[j][i]%MOD;
            add%=MOD;
        }
        res+=add*mult%MOD; res%=MOD;
    }
    res*=pw(fac[n],MOD-2); res%=MOD;
    printf("%lld\n",res);
    return 0;
}

Compilation message (stderr)

S.cpp: In function 'int main()':
S.cpp:23:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
S.cpp:25:39: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%lld %lld",&p[i],&d[i]);
                                       ^

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