Submission #19905

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19905	2016-02-25T06:56:08 Z	Qwaz	능력 (kriii4_S)	C++	100 / 100	1005 ms	394896 KB

S

#include <cstdio>

typedef long long ll;
const int MOD = 1000000007, MAX = 5020;

ll modpow(ll a, ll x) {
	ll ret = 1;
	a = a % MOD;

	while (x) {
		if (x & 1) ret = ret * a % MOD;
		a = a * a % MOD;
		x >>= 1;
	}

	return ret;
}

int success[MAX], fail[MAX], damage[MAX];
//failSum, failX는 조합의 개수를 셈
ll failSum[MAX][MAX], failX[MAX][MAX];

ll rotate(ll x) {
	return x < 0 ? x + MOD : x;
}

int main() {
	int n;
	scanf("%d", &n);

	const ll divider = modpow(1000000000, MOD-2);

	for (int i = 0; i < n; i++) {
		scanf("%d%d", &success[i], &damage[i]);
		success[i] = success[i] * divider % MOD;
		fail[i] = 1 - success[i];
		if (fail[i] < 0) fail[i] += MOD;
	}

	ll res = 0;
	ll selectRate = modpow(n, MOD-2);
	for (int i = n-1; i >= 0; i--) {
		//1번째로 i가 실패할 확률
		failX[1][i] = (selectRate * fail[i]) % MOD;
		failSum[1][i] = (failX[1][i] + failSum[1][i+1]) % MOD;

		//1번째로 i가 성공할 확률
		res = (res + selectRate * success[i] % MOD * damage[i] % MOD) % MOD;
	}

	//factorial은 (order-1)!을 저장
	ll factorial = 1;
	for (int order = 2; order <= n; order++) {
		factorial = factorial * (order-1) % MOD;
		selectRate = modpow(n-order+1, MOD-2);
		for (int i = n-1; i >= 0; i--) {
			ll tmp;
			//order개 중 i가 실패한 것이 포함된 것 확률
			tmp = rotate(failSum[order-1][0] - failX[order-1][i]) * selectRate % MOD;
			tmp = tmp * fail[i] % MOD;
			failX[order][i] = tmp;

			//order번째로 i가 성공할 확률
			tmp = factorial * rotate(failSum[order-1][0] - failX[order-1][i]) % MOD;
			tmp = tmp * selectRate % MOD;
			tmp = tmp * success[i] % MOD;
			res = (res + tmp * damage[i] % MOD) % MOD;
		}

		for (int i = n-1; i >= 0; i--) {
			failSum[order][i] = (fail[i] * selectRate) % MOD * failSum[order-1][i+1] % MOD;
			failSum[order][i] = (failSum[order][i] + failSum[order][i+1]) % MOD;
		}
	}

	printf("%lld\n", res);

	return 0;
}

Subtask #1

10.0 / 10.0

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

Subtask #2

90.0 / 90.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	965 ms	394896 KB	Output is correct
2	Correct	982 ms	394896 KB	Output is correct
3	Correct	989 ms	394896 KB	Output is correct
4	Correct	979 ms	394896 KB	Output is correct
5	Correct	978 ms	394896 KB	Output is correct
6	Correct	983 ms	394896 KB	Output is correct
7	Correct	970 ms	394896 KB	Output is correct
8	Correct	975 ms	394896 KB	Output is correct
9	Correct	955 ms	394896 KB	Output is correct
10	Correct	977 ms	394896 KB	Output is correct
11	Correct	974 ms	394896 KB	Output is correct
12	Correct	982 ms	394896 KB	Output is correct
13	Correct	972 ms	394896 KB	Output is correct
14	Correct	960 ms	394896 KB	Output is correct
15	Correct	991 ms	394896 KB	Output is correct
16	Correct	988 ms	394896 KB	Output is correct
17	Correct	973 ms	394896 KB	Output is correct
18	Correct	982 ms	394896 KB	Output is correct
19	Correct	1005 ms	394896 KB	Output is correct
20	Correct	978 ms	394896 KB	Output is correct