Submission #19008

#	Time	Username	Problem	Language	Result	Execution time	Memory
19008		kriii	능력 (kriii4_S)	C++14	100 / 100	175 ms	1280 KiB

S

#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;
}

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