# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
25977 | abcdef6199 | 마스코트 (JOI13_mascots) | C++98 | 3 ms | 108192 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int, int> II;
const int N = 3000 + 10;
const int P = (int) 1e9 + 7;
int n, m, k;
int C[N][N];
int dp[N][N];
int fac[N * N];
int main() {
scanf("%d%d", &n, &m);
int r1 = n + 1, r2 = -1;
int c1 = m + 1, c2 = -1;
scanf("%d", &k);
for (int i = 1; i <= k; ++i) {
int x, y; scanf("%d%d", &x, &y);
r1 = min(r1, x); r2 = max(r2, x);
c1 = min(c1, y); c2 = max(c2, y);
}
fac[0] = 1;
for (int i = 1; i <= n * m; ++i) fac[i] = (LL) fac[i - 1] * i % P;
for (int i = 0; i <= max(n, m); ++i) {
C[i][0] = 1;
for (int j = 1; j <= i; ++j) {
C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
if (C[i][j] >= P) C[i][j] -= P;
}
}
int lx = r2 - r1 + 1;
int ly = c2 - c1 + 1;
dp[lx][ly] = fac[lx * ly - k];
for (int i = lx; i <= n; ++i) for (int j = ly; j <= m; ++j) {
if (i < n) dp[i + 1][j] = (dp[i + 1][j] + (LL) dp[i][j] * fac[j]) % P;
if (j < m) dp[i][j + 1] = (dp[i][j + 1] + (LL) dp[i][j] * fac[i]) % P;
}
int ans = dp[n][m];
int mul = (LL) C[n - lx][r1 - 1] * C[m - ly][c1 - 1];
cout << (LL) ans * mul % P;
return 0;
}
Compilation message (stderr)
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |