#include <stdio.h>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;
const int MX = 105, MM = 1000000007;
ll rv(ll A){
ll R = 1, B = MM-2;
while(B){
if( B&1 ) R = R * A % MM;
A = A * A % MM; B /= 2;
}
return R;
}
struct frac{
ll A, B;
frac(ll A, ll B):A(A), B(B){}
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; }
};
frac D[MX][MX], I[MX][MX];
int P, Q, N, K;
void print()
{
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
printf("%lld,%lld ", D[i][j].A, D[i][j].B);
}
printf("\n");
}
printf("\n");
}
int main()
{
int M;
frac ans = frac(0, 1);
scanf("%d", &M);
for(int i = 1; i <= M; i++){
int N, S;
scanf("%d%d", &N, &S);
ans = ans + frac(S, N);
}
printf("%lld\n", ans.v());
/*
scanf("%d%d%d%d", &P, &Q, &N, &K);
for(int i = 1; i <= N; i++){
D[i][i] = I[i][i] = frac(1, 1);
if( i <= N-2 ) D[i][i+1] = frac(MM-Q, P);
if( i >= 3) D[i][i-1] = frac(MM-P+Q, P);
}
print();
for(int i = 1; i <= N; i++){
for(int j = i+1; j <= N; j++){
frac p = D[j][i] / D[i][i];
for(int k = 1; k <= N; k++){
D[j][k] = D[j][k] - D[i][k] * p;
I[j][k] = I[j][k] - I[i][k] * p;
}
}
}
for(int i = N; i >= 1; i--){
for(int j = i-1; j >= 1; j--){
frac p = D[j][i] / D[i][i];
for(int k = N; k >= 1; k--){
D[j][k] = D[j][k] - D[i][k] * p;
I[j][k] = I[j][k] - I[i][k] * p;
}
}
}
for(int i = 1; i <= N; i++){
frac p = frac(1, 1) / D[i][i];
for(int j = 1; j <= N; j++){
D[i][j] = D[i][j] * p;
I[i][j] = I[i][j] * p;
}
}
print();
for(int i = 1; i <= N; i++){
for(int j = 1; j <= N; j++){
printf("%lld ", I[i][j].v());
}
printf("\n");
}
printf("%lld", I[N][K].v());*/
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
1428 KB |
Output is correct |
2 |
Correct |
3 ms |
1428 KB |
Output is correct |
3 |
Correct |
3 ms |
1428 KB |
Output is correct |
4 |
Correct |
3 ms |
1428 KB |
Output is correct |
5 |
Correct |
3 ms |
1428 KB |
Output is correct |
6 |
Correct |
2 ms |
1428 KB |
Output is correct |
7 |
Correct |
0 ms |
1428 KB |
Output is correct |
8 |
Correct |
3 ms |
1428 KB |
Output is correct |
9 |
Correct |
3 ms |
1428 KB |
Output is correct |
10 |
Correct |
3 ms |
1428 KB |
Output is correct |
11 |
Correct |
0 ms |
1428 KB |
Output is correct |
12 |
Correct |
3 ms |
1428 KB |
Output is correct |
13 |
Correct |
0 ms |
1428 KB |
Output is correct |
14 |
Correct |
0 ms |
1428 KB |
Output is correct |
15 |
Correct |
0 ms |
1428 KB |
Output is correct |
16 |
Correct |
0 ms |
1428 KB |
Output is correct |
17 |
Correct |
0 ms |
1428 KB |
Output is correct |
18 |
Correct |
0 ms |
1428 KB |
Output is correct |
19 |
Correct |
0 ms |
1428 KB |
Output is correct |
20 |
Correct |
0 ms |
1428 KB |
Output is correct |