#include <bits/stdc++.h>
using namespace std;
const int maxn = 3005;
const int mod = 1e9 + 7;
int R, C, N;
int minX = 1e9, maxX = -1e9, minY = 1e9, maxY = -1e9;
int ft[maxn * maxn];
int bc[maxn][maxn];
int f[maxn][maxn];
int cal(int x, int y) {
if (f[x][y]) return f[x][y];
if (x == R && y == C) return 1;
if (x < R)
f[x][y] = (f[x][y] + cal(x + 1, y) * 1LL * ft[y]) % mod;
if (y < C)
f[x][y] = (f[x][y] + cal(x, y + 1) * 1LL * ft[x]) % mod;
return f[x][y];
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> R >> C;
ft[0] = 1;
for (int i = 1; i <= R * C; ++i)
ft[i] = ft[i - 1] * 1LL * i % mod;
bc[0][0] = 1;
for (int i = 1; i <= 3000; ++i) {
bc[0][i] = 1;
for (int j = 1; j <= i; ++j)
bc[j][i] = (bc[j][i - 1] + bc[j - 1][i - 1]) % mod;
}
cin >> N;
for (int i = 1; i <= N; ++i) {
int x, y; cin >> x >> y;
minX = min(minX, x); maxX = max(maxX, x);
minY = min(minY, y); maxY = max(maxY, y);
}
int ans = ft[(maxX - minX + 1) * (maxY - minY + 1) - N];
ans = ans * 1LL * cal(maxX - minX + 1, maxY - minY + 1) % mod;
ans = ans * 1LL * bc[minX - 1][R - maxX + minX - 1] % mod * bc[minY - 1][C - maxY + minY - 1] % mod;
cout << ans << endl;
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
129 ms |
107996 KB |
Output is correct |
| 2 |
Correct |
133 ms |
107996 KB |
Output is correct |
| 3 |
Correct |
113 ms |
107996 KB |
Output is correct |
| 4 |
Correct |
123 ms |
107996 KB |
Output is correct |
| 5 |
Correct |
106 ms |
107996 KB |
Output is correct |
| 6 |
Correct |
123 ms |
107996 KB |
Output is correct |
| 7 |
Correct |
123 ms |
107996 KB |
Output is correct |
| 8 |
Correct |
129 ms |
107996 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
129 ms |
107996 KB |
Output is correct |
| 2 |
Correct |
129 ms |
107996 KB |
Output is correct |
| 3 |
Correct |
123 ms |
107996 KB |
Output is correct |
| 4 |
Correct |
103 ms |
107996 KB |
Output is correct |
| 5 |
Correct |
96 ms |
107996 KB |
Output is correct |
| 6 |
Correct |
113 ms |
107996 KB |
Output is correct |
| 7 |
Correct |
99 ms |
107996 KB |
Output is correct |
| 8 |
Correct |
113 ms |
107996 KB |
Output is correct |
| 9 |
Correct |
113 ms |
107996 KB |
Output is correct |
| 10 |
Correct |
99 ms |
107996 KB |
Output is correct |
| 11 |
Correct |
109 ms |
107996 KB |
Output is correct |
| 12 |
Correct |
119 ms |
107996 KB |
Output is correct |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
116 ms |
107996 KB |
Output is correct |
| 2 |
Correct |
106 ms |
107996 KB |
Output is correct |
| 3 |
Correct |
119 ms |
107996 KB |
Output is correct |
| 4 |
Correct |
133 ms |
107996 KB |
Output is correct |
| 5 |
Correct |
143 ms |
107996 KB |
Output is correct |
| 6 |
Correct |
139 ms |
107996 KB |
Output is correct |
| 7 |
Correct |
119 ms |
107996 KB |
Output is correct |
| 8 |
Correct |
136 ms |
107996 KB |
Output is correct |
| 9 |
Correct |
193 ms |
107996 KB |
Output is correct |
| 10 |
Correct |
313 ms |
108216 KB |
Output is correct |
| 11 |
Correct |
249 ms |
108148 KB |
Output is correct |
| 12 |
Correct |
186 ms |
107996 KB |
Output is correct |
| 13 |
Correct |
119 ms |
107996 KB |
Output is correct |
| 14 |
Correct |
169 ms |
107996 KB |
Output is correct |
| 15 |
Correct |
303 ms |
108212 KB |
Output is correct |
| 16 |
Correct |
266 ms |
108176 KB |
Output is correct |
| 17 |
Correct |
179 ms |
107996 KB |
Output is correct |
| 18 |
Correct |
319 ms |
108204 KB |
Output is correct |
