Submission #34003

#TimeUsernameProblemLanguageResultExecution timeMemory
34003ngkan146마스코트 (JOI13_mascots)C++98
100 / 100
89 ms37472 KiB
// aome & ngkan #include <bits/stdc++.h> using namespace std; const int N = 3005; const int mod = 1e9 + 7; int n, m, q, res = 1; int prd[N], inv[N]; int f[N][N]; int mnX, mxX, mnY, mxY; int lenX, lenY; int pw(int x, int y) { if (!y) return 1; int ret = pw(x, y >> 1); ret = 1LL * ret * ret % mod; if (y & 1) ret = 1LL * ret * x % mod; return ret; } int C(int n, int k) { if (n < k) return 0; return 1LL * prd[n] * inv[n - k] % mod * inv[k] % mod; } int main() { ios::sync_with_stdio(false); cin >> n >> m >> q; prd[0] = inv[0] = 1; for (int i = 1; i < N; ++i) { prd[i] = 1LL * prd[i - 1] * i % mod, inv[i] = pw(prd[i], mod - 2); } mnX = mnY = 1e9; for (int i = 1; i <= q; ++i) { int x, y; cin >> x >> y; mnX = min(mnX, x), mnY = min(mnY, y); mxX = max(mxX, x), mxY = max(mxY, y); } lenX = mxX - mnX + 1, lenY = mxY - mnY + 1; int cntIn = lenX * lenY - q; for (int i = 1; i <= cntIn; ++i) res = 1LL * res * i % mod; f[lenX][lenY] = 1; for (int i = lenX; i <= n; ++i) { for (int j = lenY; j <= m; ++j) { if (i == lenX && j == lenY) continue; if (i != lenX) f[i][j] = (f[i][j] + 1LL * f[i - 1][j] * prd[j]) % mod; if (j != lenY) f[i][j] = (f[i][j] + 1LL * f[i][j - 1] * prd[i]) % mod; } } res = 1LL * res * f[n][m] % mod; res = 1LL * res * C(n - lenX, n - mxX) % mod * C(m - lenY, m - mxY) % mod; cout << res; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...