Submission #21288

#	Time	Username	Problem	Language	Result	Execution time	Memory
21288		gs14004	능력 (kriii4_S)	C++11	10 / 100	2000 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 d1[5005][5005], d2[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;
	}
	d1[0][0] = 1;
	for(int i=1; i<=n; i++){
		for(int j=0; j<=n; j++){
			d1[i][j] = d1[i-1][j];
			if(j > 0) d1[i][j] += d1[i-1][j-1] * (mod + 1 - p[i]);
			d1[i][j] %= mod;
		}
	}
	d2[n+1][0] = 1;
	for(int i=n; i>=1; i--){
		for(int j=0; j<=n; j++){
			d2[i][j] = d2[i+1][j];
			if(j > 0) d2[i][j] += d2[i+1][j-1] * (mod + 1 - p[i]);
			d2[i][j] %= mod;
		}
	}
	lint ret = 0;
	for(int i=1; i<=n; i++){
		lint cur = 0;
		for(int j=0; j<n; j++){
			for(int k=0; k<n; k++){
				lint cp = d1[i-1][j] * d2[i+1][k] % mod;
				cp *= fact[j + k];
				cp %= mod;
				cp *= fact[n - 1 - j - k];
				cp %= mod;
				cur += cp;
				cur %= mod;
			}
		}
		ret += cur * (p[i] * d[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: 0 / 90