Submission #19414

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
19414	2016-02-24T11:28:35 Z	kdh9949	Σ (kriii4_P2)	C++	100 / 100	6 ms	1396 KB

P2

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;

int n;
ll a[10010], b[10010], pfmul[10010], sfmul[10010];
ll ansa, ansb;
ll mod = 1000000007;

ll pw(ll x, ll k){
    if(k == 0) return 1;
    if(k == 1) return x;
    ll t = pw(x, k / 2); t *= t; t %= mod;
    if(k % 2) return t * x % mod;
    return t;
}

ll modinv(ll x){
    return pw(x % mod, mod - 2);
}

int main(){
    scanf("%d", &n);
    for(int i = 1; i <= n; i++){
        scanf("%lld%lld", b + i, a + i);
    }
    ansb = 1;
    for(int i = 1; i <= n; i++){
        ansb *= b[i];
        ansb %= mod;
    }
    pfmul[0] = sfmul[n + 1] = 1;
    for(int i = 1; i <= n; i++) pfmul[i] = pfmul[i - 1] * b[i] % mod, sfmul[n + 1 - i] = sfmul[n + 2 - i] * b[n + 1 - i] % mod;
    for(int i = 1; i <= n; i++){
        ansa += pfmul[i - 1] * a[i] % mod * sfmul[i + 1] % mod;
        ansa %= mod;
    }
    printf("%lld\n", (ansa * modinv(ansb)) % mod);
}

Subtask #1

100.0 / 100.0

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