oj.uz

Submission #20149

# Submission time Handle Problem Language Result Execution time Memory
20149 2016-02-28T11:45:49 Z emppu 능력 (kriii4_S) C++14
100 / 100
 596 ms 1856 KB 
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <cstring>
#include <cassert>

#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <tuple>
#include <queue>
#include <deque>
#include <list>

#define f0(_X,_Y) for(int (_X)=0;(_X)<(_Y);++(_X))
#define f1(_X,_Y) for(int (_X)=1;(_X)<=(_Y);++(_X))
#define ff(_X,_Y,_Z) for(int (_X)=(_Y);(_X)<=(_Z);++(_X))
#define fF(_X,_Y,_Z) for(int (_X)=(_Y);(_X)<(_Z);++(_X))
#define rf0(_X,_Y) for(int _X=(_Y)-1;(_X)>=0;--(_X))
#define rf1(_X,_Y) for(int _X=(_Y);(_X)>0;--(_X))
#define rff(_X,_Y,_Z) for(int _X=(_Y);(_X)>=(_Z);--(_X))
#define rfF(_X,_Y,_Z) for(int _X=(_Y);(_X)>(_Z);--(_X))

#define PRT(_X) cout<< #_X ": "<<_X<<endl;
#define TIME fprintf(stderr,"time : %.2f sec\n",double(clock())/CLOCKS_PER_SEC)
#define FIN freopen("input","r",stdin)

#define scan1(_X) scanf("%d",&_X);
#define scan2(_X,_Y) scanf("%d%d",&_X,&_Y);
#define scan3(_X,_Y,_Z) scanf("%d%d%d",&_X,&_Y,&_Z);
#define define1(_1) int _1; scan1(_1)
#define define2(_1,_2) int _1,_2; scan2(_1,_2)
#define define3(_1,_2,_3) int _1,_2,_3; scan3(_1,_2,_3)
#define EXPAND(_1) _1
#define SELECT(_1,_2,_3,_4,NAME,...) NAME
#define scan(...) EXPAND(SELECT(__VA_ARGS__, scan4, scan3, scan2, scan1)(__VA_ARGS__))
#define define(...) EXPAND(SELECT(__VA_ARGS__, define4, define3, define2, define1)(__VA_ARGS__))
#define print(_X) printf("%d\n",_X)
#define PAIR_STRUCT(_T,_X,_Y,...) struct _T{int _X,_Y,##__VA_ARGS__; bool friend operator < (const _T &p, const _T &q){if(p._X!=q._X) return p._X<q._X; return p._Y<q._Y;}}

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;

const int N = 5005;
int p[N],pR[N];
int d[N],d2[N];

const int MOD = 1000000007;
ll mul(ll a, ll b){return a*b%MOD;}
ll add(ll a, ll b){return (a+b)%MOD;}
ll inv(ll a, ll b=MOD)
{
	ll s = 0;  ll  old_s = 1;
	ll r = b;  ll  old_r = a;
	while (r!=0)
	{
		ll quotient = old_r / r;
		tie(old_r, r) = make_tuple(r, old_r - quotient * r);
		tie(old_s, s) = make_tuple(s, old_s - quotient * s);
	}
	ll inv = old_s%MOD;
	if(inv<0) inv += MOD;
	return inv;
}


int dv[N];
int deal[N];
int _inv[N];
int main()
{
	// divisors
	ff(i,2,5000)
	{
		for(int j=i;j<=5000;j+=i) if(!dv[j]) dv[j]=i;
	}
	// inverse
	_inv[1]=1;
	ff(i,2,5000)
	{
		if(dv[i]!=i)
			_inv[i]=  mul(_inv[dv[i]],_inv[i/dv[i]]);
		else
			_inv[i]= inv(i);
	}

	define(n);
	const int denominator = 1000000000;
	const ll denominator_inv = inv(denominator);
	f1(i,n) { scan(p[i],deal[i]); pR[i] = mul(denominator-p[i],denominator_inv); p[i]=mul(p[i],denominator_inv); }

	d[0]=1;
	f1(i,n) rf1(j,i) d[j] = add(d[j],mul(pR[i],d[j-1]));
	ll ans=0;
	f1(i,n)
	{
		ll nCm_inv = _inv[n];
		// 1/nCm = 1*2*..*m/(n*(n-1)..(n-m+1))
		ll dmg = 0;
		ff(m,0,n-1)
		{
			if(!m)
				d2[m]=1;
			else
			{
				d2[m] = add(d[m],MOD - mul(d2[m-1],pR[i]));
				nCm_inv = mul(mul(nCm_inv, m), _inv[n-m]);
			}
			dmg = add(dmg,mul(d2[m],nCm_inv));
		}
		ans = add(ans, mul(dmg,mul(p[i],deal[i])));
	}

	printf("%lld\n",ans);

	return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1856 KB Output is correct
2 Correct 2 ms 1856 KB Output is correct
3 Correct 0 ms 1856 KB Output is correct
4 Correct 0 ms 1856 KB Output is correct
5 Correct 0 ms 1856 KB Output is correct
6 Correct 0 ms 1856 KB Output is correct
7 Correct 0 ms 1856 KB Output is correct
8 Correct 2 ms 1856 KB Output is correct
9 Correct 0 ms 1856 KB Output is correct
10 Correct 0 ms 1856 KB Output is correct
11 Correct 0 ms 1856 KB Output is correct
12 Correct 0 ms 1856 KB Output is correct
13 Correct 0 ms 1856 KB Output is correct
14 Correct 1 ms 1856 KB Output is correct
15 Correct 0 ms 1856 KB Output is correct
16 Correct 0 ms 1856 KB Output is correct
17 Correct 0 ms 1856 KB Output is correct
18 Correct 0 ms 1856 KB Output is correct
19 Correct 1 ms 1856 KB Output is correct
20 Correct 0 ms 1856 KB Output is correct

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 596 ms 1856 KB Output is correct
2 Correct 594 ms 1856 KB Output is correct
3 Correct 591 ms 1856 KB Output is correct
4 Correct 595 ms 1856 KB Output is correct
5 Correct 593 ms 1856 KB Output is correct
6 Correct 594 ms 1856 KB Output is correct
7 Correct 592 ms 1856 KB Output is correct
8 Correct 595 ms 1856 KB Output is correct
9 Correct 591 ms 1856 KB Output is correct
10 Correct 593 ms 1856 KB Output is correct
11 Correct 594 ms 1856 KB Output is correct
12 Correct 593 ms 1856 KB Output is correct
13 Correct 591 ms 1856 KB Output is correct
14 Correct 593 ms 1856 KB Output is correct
15 Correct 591 ms 1856 KB Output is correct
16 Correct 589 ms 1856 KB Output is correct
17 Correct 595 ms 1856 KB Output is correct
18 Correct 592 ms 1856 KB Output is correct
19 Correct 590 ms 1856 KB Output is correct
20 Correct 592 ms 1856 KB Output is correct