Submission #19905

#	Time	Username	Problem	Language	Result	Execution time	Memory
19905		Qwaz	능력 (kriii4_S)	C++98	100 / 100	1005 ms	394896 KiB

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 / 10
• Subtask 2: 90 / 90