제출 #19962

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
19962		tonyjjw	능력 (kriii4_S)	C++14	100 / 100	644 ms	391980 KiB

S

//*
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<algorithm>
#include<vector>
#define all(A) (A).begin(), (A).end()

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;
const int MN = 5000+1;
const ll mod = 1000000007;

int N;
ll p[MN],d[MN];

ll mpow(ll a,ll p){
	ll r=1;
	while(p>0){
		if(p&1)r=r*a%mod;
		a=a*a%mod;
		p>>=1;
	}
	return r;
}

ll inverse(ll a){
	return mpow(a,mod-2);
}

const ll ti = inverse(1000000000);

ll D[MN][MN];
ll A[MN][MN];
ll fact[MN];

int main(){
	scanf("%d",&N);
	fact[0]=1;
	for(int i=1;i<=N;i++)fact[i]=fact[i-1]*i%mod;
	for(int i=0;i<N;i++){
		scanf("%lld%lld",&p[i],&d[i]);
		p[i]=p[i]*ti%mod;
		d[i]=d[i]*p[i]%mod;
	}
	D[0][0]=1;
	D[0][1]=1-p[0];
	for(int i=1;i<N;i++){
		D[i][0]=1;
		for(int j=1;j<=i+1;j++){
			D[i][j]=(1-p[i])*D[i-1][j-1]+D[i-1][j];
			D[i][j]%=mod;
		}
	}
	for(int i=0;i<N;i++){
		A[i][0]=1;
		for(int j=1;j<N;j++){
			A[i][j]=D[N-1][j]-(1-p[i])*A[i][j-1];
			A[i][j]%=mod;
		}
	}
	ll ans=0;
	for(int i=0;i<N;i++)for(int j=0;j<N;j++){
		ans+=d[i]*fact[j]%mod*fact[N-j-1]%mod*A[i][j]%mod;
		ans%=mod;
	}
	if(ans<0)ans+=mod;
	ans=ans*inverse(fact[N])%mod;
	printf("%lld\n",ans);
	return 0;
}
//*/

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