제출 #19008

#제출 시각아이디문제언어결과실행 시간메모리
19008kriii능력 (kriii4_S)C++14
100 / 100
175 ms1280 KiB
#include <stdio.h>
#include <algorithm>
using namespace std;

const long long mod = 1000000007;

long long fpow(long long a, long long p)
{
	a %= mod;
	p = (p % (mod - 1) + mod - 1) % (mod - 1);
	long long r = 1;
	while (p){
		if (p & 1) r = r * a % mod;
		a = a * a % mod;
		p /= 2;
	}
	return r;
}

long long inv[5005],p[5005],d[5005],bit[2][5005];

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

	inv[1] = 1;
	for (int i=2;i<=n;i++) inv[i] = (mod - mod / i) * inv[mod % i] % mod;

	long long pc=fpow(1000000000,-1);
	for (int i=0;i<n;i++){
		scanf ("%lld %lld",&p[i],&d[i]);
		p[i] = p[i] * pc % mod;
	}

	long long sum = 0;
	for (int i=0;i<=n;i++) bit[0][i] = bit[1][i] = 0;
	bit[0][0] = 1;
	for (int i=0;i<n;i++){
		for (int j=i;j>=0;j--){
			bit[1][j+1] = (bit[1][j+1] + bit[0][j] * p[i] % mod * d[i]) % mod;
			bit[1][j+1] = (bit[1][j+1] + bit[1][j] * p[i]) % mod;
			bit[0][j+1] = (bit[0][j+1] + bit[0][j] * p[i]) % mod;
		}
	}
	for (int i=1;i<=n;i++){
		long long add = bit[1][i] * inv[i] % mod;
		if (i & 1) sum = (sum + add) % mod;
		else sum = (sum + mod - add) % mod;
	}
	printf ("%lld\n",sum);

	return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...