Submission #21284

#	Time	Username	Problem	Language	Result	Execution time	Memory
21284		suzy	능력 (kriii4_S)	C++11	10 / 100	2000 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 ri(int k, int i) {
    if(k==0) return 1;
    if(rd[k][i]>=0) return rd[k][i];
    return rd[k][i]=(r[k][n]-ri(k-1,i)*q[i]%MOD+MOD)%MOD;
}

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;
    }
    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*ri(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:29:19: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d",&n);
                   ^
S.cpp:31: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: 0 / 90