oj.uz

Submission #19279

# Submission time Handle Problem Language Result Execution time Memory
19279 2016-02-24T02:13:31 Z kaTkaHr 능력 (kriii4_S) C++14
100 / 100
 1167 ms 55772 KB 
#include <stdio.h>
#include<vector>
#include <algorithm>
#include <map>

using namespace std;

typedef long long ll;

const int MX = 1000005, MM = 1000000007;

ll pw(ll A, ll B){
    ll R = 1;
    while(B){
        if( B&1 ) R = R * A % MM;
        A = A * A % MM; B /= 2;
    }
    return R;
}


ll rv(ll A){ return pw(A, MM-2); }
/*
struct frac{
    ll A, B;
		frac(ll A):A(A), B(1){}
    frac(ll a, ll b){
        A = (a%MM+MM) % MM;
        B = (b%MM+MM) % MM;
    }
    frac(){A = 0, B = 1;}
    frac operator+ (const frac &l)const{
        return frac((A * l.B + B * l.A) % MM, B * l.B % MM);
    }
    frac operator*(const frac &l)const{
        return frac(A*l.A % MM, B*l.B % MM);
    }
    frac operator/(const frac &l)const{
        return frac(A*l.B % MM, B*l.A % MM);
    }
    frac operator- (const frac &l)const{
        return frac((A*l.B - B*l.A%MM + MM) % MM, B*l.B % MM);
    }
    ll v(){ return A * rv(B) % MM; }
};// */
//*
struct frac{
    ll A;
		frac(ll A):A((A+MM)%MM){}
    frac(ll a, ll b){
			A = rv(b) * a % MM;
    }
    frac(){A = 0;}
    frac operator+ (const frac &l)const{
			return l.A + A >= MM? l.A + A - MM: l.A + A;
    }
    frac operator*(const frac &l)const{
			return l.A * A % MM;
    }
    frac operator/(const frac &l)const{
			return A * rv(l.A) % MM;
    }
    frac operator- (const frac &l)const{
			return A >= l.A? A-l.A: A-l.A + MM;
    }
    ll v(){ return A; }
};// */

frac pw(frac A, ll B){
    frac R = 1;
    while(B){
        if( B&1 ) R = R * A;
        A = A * A; B /= 2;
    }
    return R;
}

frac P[MX], Q[MX], A[MX], B[MX], C[MX], D[MX], R[MX];

int main()
{
	int N, p, q;

	scanf("%d", &N);
	for(int i = 1; i <= N; i++){
		scanf("%d%d", &p, &q);
		P[i] = frac(p, 1000000000);
		Q[i] = q;
	}
	
	for(int i = 1; i <= N; i++){
		frac mul = 1;
		for(int j = 1; j <= N; j++){
			mul = mul * P[i];
			B[j] = B[j] + mul;
			D[j] = D[j] + mul * Q[i];
		}
	}

	A[0] = 1;
	for(int i = 1; i <= N; i++){
		int p = 1;
		for(int j = i-1; j >= 0; j--){
			A[i] = A[i] + A[j] * B[i-j] * p;
			p = -p;
		}
		A[i] = A[i] / i;
	}
	
	for(int i = 1; i <= N; i++){
		int p = 1;
		for(int j = i-1; j >= 0; j--){
			C[i] = C[i] + A[j] * D[i-j] * p;
			p = -p;
		}
	}
	frac ans = 0;
	p = 1;
	for(int i = 1; i <= N; i++){
		ans = ans + C[i] / i * p;
		p = -p;
	}
	if( ans.v() == 0 ) for(;;);
	printf("%lld\n", ans.v());
}

Subtask #1
10.0 / 10.0

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

Subtask #2
90.0 / 90.0

# Verdict Execution time Memory Grader output
1 Correct 1167 ms 55772 KB Output is correct
2 Correct 1165 ms 55772 KB Output is correct
3 Correct 1163 ms 55772 KB Output is correct
4 Correct 1163 ms 55772 KB Output is correct
5 Correct 1164 ms 55772 KB Output is correct
6 Correct 1163 ms 55772 KB Output is correct
7 Correct 1162 ms 55772 KB Output is correct
8 Correct 1159 ms 55772 KB Output is correct
9 Correct 1154 ms 55772 KB Output is correct
10 Correct 1166 ms 55772 KB Output is correct
11 Correct 1163 ms 55772 KB Output is correct
12 Correct 1154 ms 55772 KB Output is correct
13 Correct 1155 ms 55772 KB Output is correct
14 Correct 1154 ms 55772 KB Output is correct
15 Correct 1166 ms 55772 KB Output is correct
16 Correct 1163 ms 55772 KB Output is correct
17 Correct 1156 ms 55772 KB Output is correct
18 Correct 1157 ms 55772 KB Output is correct
19 Correct 1146 ms 55772 KB Output is correct
20 Correct 1159 ms 55772 KB Output is correct