Submission #21290

#	Time	Username	Problem	Language	Result	Execution time	Memory
21290		gs14004	능력 (kriii4_S)	C++11	100 / 100	229 ms	393544 KiB

S

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}

int n;
lint p[5005], d[5005], fact[5005];
lint dp[2][5005][5005];

int main(){
	cin >> n;
	lint ans = 0;
	fact[0] = 1;
	for(int i=1; i<=n; i++){
		fact[i] = fact[i-1] * i % mod;
		cin >> p[i] >> d[i];
		p[i] *= ipow(1000000000, mod - 2);
		p[i] %= mod;
	}
	dp[0][0][0] = 1;
	for(int i=1; i<=n; i++){
		for(int j=0; j<=n; j++){
			dp[0][i][j] = dp[0][i-1][j];
			if(j > 0) dp[0][i][j] += dp[0][i-1][j-1] * (mod + 1 - p[i]);
			dp[0][i][j] %= mod;
			dp[1][i][j] = dp[1][i-1][j] + dp[0][i-1][j] * (p[i] * d[i] % mod);
			if(j > 0) dp[1][i][j] += dp[1][i-1][j-1] * (mod + 1 - p[i]);
			dp[1][i][j] %= mod;
		}
	}
	lint ret = 0;
	for(int i=0; i<n; i++){
		ret += dp[1][n][i] * (fact[i] * fact[n-1-i] % mod) % mod;
		ret %= mod;
	}
	ret *= ipow(fact[n], mod - 2);
	ret %= mod;
	cout << ret;
}

Compilation message (stderr)

S.cpp: In function 'int main()':
S.cpp:26:7: warning: unused variable 'ans' [-Wunused-variable]
  lint ans = 0;
       ^

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