Hướng dẫn giải của Robocon
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Đếm số đường đi từ ô ~(1,1)~ đến ô ~(m,n)~, mỗi bước sang phải hoặc xuống dưới, không đi qua ô có vật cản; kết quả theo modulo ~10^9+7~.
Sub 1: Quy hoạch động trên lưới — ~O(m \cdot n)~, dùng khi ~m, n \le 1000~
~f[i][j]~ là số đường đến ô ~(i,j)~: bằng 0 nếu ô có vật cản, ngược lại bằng ~f[i-1][j] + f[i][j-1]~. Nếu chỉ nộp sub này: đúng 8/20 test.
Sub 2: Bù trừ theo vật cản — ~O(k^2)~
Số đường đi tự do từ ~(x_1,y_1)~ đến ~(x_2,y_2)~ là ~\binom{(x_2-x_1)+(y_2-y_1)}{x_2-x_1}~ (tính nhờ giai thừa và nghịch đảo modular đến ~m+n~). Sắp xếp vật cản theo tọa độ và thêm ô đích vào cuối. Gọi ~g_i~ là số đường từ ~(1,1)~ đến ô ~i~ không đi qua vật cản nào trước đó: ~g_i = \text{tất cả} - \sum_{j<i} g_j \cdot \text{ways}(j, i)~. Đáp án là ~g~ của ô đích. Nếu chỉ nộp sub này: đúng 20/20 test.</p>
Chương trình hoàn chỉnh
Hàm main đọc file ROBOCON.INP, ghi ROBOCON.OUT; ~m, n \le 1000~ gọi sub1 (8 test), còn lại gọi sub2 (12 test). Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1000000007;
int m, n, k;
vector<pair<int, int>> ob;
// Sub 1: quy hoạch động trên lưới — O(m * n), dùng khi m, n <= 1000
void sub1() {
vector<vector<char>> bad(m + 1, vector<char>(n + 1, 0));
for (auto &p : ob) bad[p.first][p.second] = 1;
vector<vector<long long>> f(m + 1, vector<long long>(n + 1, 0));
f[1][1] = 1;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++) {
if (bad[i][j]) { f[i][j] = 0; continue; }
if (i == 1 && j == 1) continue;
f[i][j] = ((i > 1 ? f[i - 1][j] : 0) + (j > 1 ? f[i][j - 1] : 0)) % MOD;
}
cout << f[m][n] << "\n";
}
long long fact[200005], inv[200005];
long long power(long long b, long long e) {
long long r = 1; b %= MOD;
for (; e; e >>= 1, b = b * b % MOD) if (e & 1) r = r * b % MOD;
return r;
}
long long C(int a, int b) {
if (b < 0 || b > a) return 0;
return fact[a] * inv[b] % MOD * inv[a - b] % MOD;
}
long long ways(pair<int, int> a, pair<int, int> b) { // số đường đi từ a đến b (chỉ sang phải/xuống)
int dx = b.first - a.first, dy = b.second - a.second;
if (dx < 0 || dy < 0) return 0;
return C(dx + dy, dx);
}
// Sub 2: bù trừ theo vật cản — O(k^2)
// Sắp xếp vật cản; g[i] = số đường từ (1,1) đến vật cản i mà không đi qua vật cản nào khác
// = tất cả đường đi - tổng g[j] * ways(j, i) với các vật cản j đứng trước i.
// Thêm ô đích (m,n) như một "vật cản" cuối cùng, g của nó chính là đáp án.
void sub2() {
int F = m + n;
fact[0] = 1;
for (int i = 1; i <= F; i++) fact[i] = fact[i - 1] * i % MOD;
inv[F] = power(fact[F], MOD - 2);
for (int i = F; i > 0; i--) inv[i - 1] = inv[i] * i % MOD;
vector<pair<int, int>> p = ob;
p.push_back({m, n});
sort(p.begin(), p.end());
p.erase(unique(p.begin(), p.end()), p.end());
int t = p.size();
vector<long long> g(t);
for (int i = 0; i < t; i++) {
g[i] = ways({1, 1}, p[i]);
for (int j = 0; j < i; j++)
g[i] = (g[i] - g[j] * ways(p[j], p[i]) % MOD + MOD) % MOD;
}
cout << g[t - 1] << "\n";
}
int main() {
freopen("ROBOCON.INP", "r", stdin);
freopen("ROBOCON.OUT", "w", stdout);
ios::sync_with_stdio(false); cin.tie(nullptr);
cin >> m >> n >> k;
ob.resize(k);
for (auto &p : ob) cin >> p.first >> p.second;
if (m <= 1000 && n <= 1000) sub1();
else sub2();
return 0;
}
Bình luận