| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 20107 |
2016-02-25T13:42:13 Z |
fredldh |
능력 (kriii4_S) |
C++ |
|
377 ms |
392020 KB |
#include<stdio.h>
#define N 5000
#define M 1000000007
//#define mod(a) ((a)%M)
typedef long long int lld;
lld mod(lld a) {
while(a < 0) a += M;
return a % M;
}
lld pow(lld a, lld x) {
if(!x) return 1;
lld P = pow(a, x/2);
if(x&1) return mod(a*mod(P*P));
return mod(P*P);
}
lld inv(lld a) {
return pow(a, M-2);
}
lld div(lld a, lld b) {
return mod(a*inv(b));
}
int n;
lld fac[N+1];
lld p[N+1], d[N+1], np[N+1];
lld f1[N+1][N+1], f2[N+1][N+1];
int main() {
scanf("%d", &n);
for(int i = 1; i <= n; ++i) {
scanf("%lld%lld", &p[i], &d[i]);
np[i] = div(pow(10,9)-p[i], pow(10,9));
p[i] = div(p[i], pow(10,9));
}
fac[0] = 1;
for(int i = 1; i <= n; ++i) fac[i] = mod(fac[i-1]*i);
for(int i = 1; i <= n; ++i) {
f1[i][1] = mod(f1[i-1][1] + np[i]);
f2[i][1] = mod(f2[i-1][1] + mod(p[i]*d[i]));
for(int j = 2; j <= i; ++j) {
f1[i][j] = mod(f1[i-1][j] + mod(f1[i-1][j-1]*mod(j*np[i])));
f2[i][j] = mod(f2[i-1][j] + mod(mod(f1[i-1][j-1]*mod(p[i]*d[i])) + mod(f2[i-1][j-1]*mod((j-1)*np[i]))));
}
}
lld res = 0;
for(int i = 1; i <= n; ++i) {
res = mod(res + div(mod(f2[n][i]*fac[n-i]), fac[n]));
}
printf("%lld\n", res);
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
3 ms |
392020 KB |
Output is correct |
| 2 |
Correct |
3 ms |
392020 KB |
Output is correct |
| 3 |
Correct |
0 ms |
392020 KB |
Output is correct |
| 4 |
Correct |
0 ms |
392020 KB |
Output is correct |
| 5 |
Correct |
0 ms |
392020 KB |
Output is correct |
| 6 |
Correct |
0 ms |
392020 KB |
Output is correct |
| 7 |
Correct |
3 ms |
392020 KB |
Output is correct |
| 8 |
Correct |
0 ms |
392020 KB |
Output is correct |
| 9 |
Correct |
3 ms |
392020 KB |
Output is correct |
| 10 |
Correct |
0 ms |
392020 KB |
Output is correct |
| 11 |
Correct |
0 ms |
392020 KB |
Output is correct |
| 12 |
Correct |
0 ms |
392020 KB |
Output is correct |
| 13 |
Correct |
0 ms |
392020 KB |
Output is correct |
| 14 |
Correct |
0 ms |
392020 KB |
Output is correct |
| 15 |
Correct |
0 ms |
392020 KB |
Output is correct |
| 16 |
Correct |
3 ms |
392020 KB |
Output is correct |
| 17 |
Correct |
0 ms |
392020 KB |
Output is correct |
| 18 |
Correct |
3 ms |
392020 KB |
Output is correct |
| 19 |
Correct |
0 ms |
392020 KB |
Output is correct |
| 20 |
Correct |
3 ms |
392020 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
360 ms |
392020 KB |
Output is correct |
| 2 |
Correct |
371 ms |
392020 KB |
Output is correct |
| 3 |
Correct |
370 ms |
392020 KB |
Output is correct |
| 4 |
Correct |
360 ms |
392020 KB |
Output is correct |
| 5 |
Correct |
355 ms |
392020 KB |
Output is correct |
| 6 |
Correct |
355 ms |
392020 KB |
Output is correct |
| 7 |
Correct |
371 ms |
392020 KB |
Output is correct |
| 8 |
Correct |
325 ms |
392020 KB |
Output is correct |
| 9 |
Correct |
356 ms |
392020 KB |
Output is correct |
| 10 |
Correct |
365 ms |
392020 KB |
Output is correct |
| 11 |
Correct |
372 ms |
392020 KB |
Output is correct |
| 12 |
Correct |
367 ms |
392020 KB |
Output is correct |
| 13 |
Correct |
377 ms |
392020 KB |
Output is correct |
| 14 |
Correct |
355 ms |
392020 KB |
Output is correct |
| 15 |
Correct |
353 ms |
392020 KB |
Output is correct |
| 16 |
Correct |
337 ms |
392020 KB |
Output is correct |
| 17 |
Correct |
318 ms |
392020 KB |
Output is correct |
| 18 |
Correct |
368 ms |
392020 KB |
Output is correct |
| 19 |
Correct |
360 ms |
392020 KB |
Output is correct |
| 20 |
Correct |
358 ms |
392020 KB |
Output is correct |
