Submission #19962

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19962	2016-02-25T07:51:12 Z	tonyjjw	능력 (kriii4_S)	C++14	100 / 100	644 ms	391980 KB

S

//*
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<vector>
#define all(A) (A).begin(), (A).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MN = 5000+1;
const ll mod = 1000000007;

int N;
ll p[MN],d[MN];

ll mpow(ll a,ll p){
	ll r=1;
	while(p>0){
		if(p&1)r=r*a%mod;
		a=a*a%mod;
		p>>=1;
	}
	return r;
}

ll inverse(ll a){
	return mpow(a,mod-2);
}

const ll ti = inverse(1000000000);

ll D[MN][MN];
ll A[MN][MN];
ll fact[MN];

int main(){
	scanf("%d",&N);
	fact[0]=1;
	for(int i=1;i<=N;i++)fact[i]=fact[i-1]*i%mod;
	for(int i=0;i<N;i++){
		scanf("%lld%lld",&p[i],&d[i]);
		p[i]=p[i]*ti%mod;
		d[i]=d[i]*p[i]%mod;
	}
	D[0][0]=1;
	D[0][1]=1-p[0];
	for(int i=1;i<N;i++){
		D[i][0]=1;
		for(int j=1;j<=i+1;j++){
			D[i][j]=(1-p[i])*D[i-1][j-1]+D[i-1][j];
			D[i][j]%=mod;
		}
	}
	for(int i=0;i<N;i++){
		A[i][0]=1;
		for(int j=1;j<N;j++){
			A[i][j]=D[N-1][j]-(1-p[i])*A[i][j-1];
			A[i][j]%=mod;
		}
	}
	ll ans=0;
	for(int i=0;i<N;i++)for(int j=0;j<N;j++){
		ans+=d[i]*fact[j]%mod*fact[N-j-1]%mod*A[i][j]%mod;
		ans%=mod;
	}
	if(ans<0)ans+=mod;
	ans=ans*inverse(fact[N])%mod;
	printf("%lld\n",ans);
	return 0;
}
//*/

Subtask #1

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	391980 KB	Output is correct
2	Correct	0 ms	391980 KB	Output is correct
3	Correct	0 ms	391980 KB	Output is correct
4	Correct	4 ms	391980 KB	Output is correct
5	Correct	0 ms	391980 KB	Output is correct
6	Correct	0 ms	391980 KB	Output is correct
7	Correct	0 ms	391980 KB	Output is correct
8	Correct	4 ms	391980 KB	Output is correct
9	Correct	0 ms	391980 KB	Output is correct
10	Correct	4 ms	391980 KB	Output is correct
11	Correct	0 ms	391980 KB	Output is correct
12	Correct	0 ms	391980 KB	Output is correct
13	Correct	0 ms	391980 KB	Output is correct
14	Correct	4 ms	391980 KB	Output is correct
15	Correct	0 ms	391980 KB	Output is correct
16	Correct	0 ms	391980 KB	Output is correct
17	Correct	0 ms	391980 KB	Output is correct
18	Correct	3 ms	391980 KB	Output is correct
19	Correct	0 ms	391980 KB	Output is correct
20	Correct	0 ms	391980 KB	Output is correct

Subtask #2

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	636 ms	391980 KB	Output is correct
2	Correct	619 ms	391980 KB	Output is correct
3	Correct	633 ms	391980 KB	Output is correct
4	Correct	627 ms	391980 KB	Output is correct
5	Correct	635 ms	391980 KB	Output is correct
6	Correct	636 ms	391980 KB	Output is correct
7	Correct	637 ms	391980 KB	Output is correct
8	Correct	640 ms	391980 KB	Output is correct
9	Correct	633 ms	391980 KB	Output is correct
10	Correct	620 ms	391980 KB	Output is correct
11	Correct	627 ms	391980 KB	Output is correct
12	Correct	637 ms	391980 KB	Output is correct
13	Correct	623 ms	391980 KB	Output is correct
14	Correct	637 ms	391980 KB	Output is correct
15	Correct	644 ms	391980 KB	Output is correct
16	Correct	625 ms	391980 KB	Output is correct
17	Correct	623 ms	391980 KB	Output is correct
18	Correct	629 ms	391980 KB	Output is correct
19	Correct	621 ms	391980 KB	Output is correct
20	Correct	641 ms	391980 KB	Output is correct