Hướng dẫn giải của Atcoder Educational DP Contest Y - Grid 2
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.
Phân tích:
Số cách để đi từ ô ~(i,j)~ đến ô ~(x,y)~ là ~\begin{pmatrix}x-i\\ x-i+y-j\end{pmatrix}~ có thể tính trong ~\mathcal O(1)~ nếu tính toán trước.
Giả sử ta có thể đi được đến các ô có chướng ngại vật. Gọi ~\texttt{dp}[i]~ là số cách đi từ ô ~(1,1)~ đến chướng ngại vật thứ ~i~ mà không đi qua bất cứ chướng ngại vật nào khác ngoài chướng ngại vật thứ ~i~.
Để ý rằng nếu không có chướng ngại vật nào giữa ô ~(1,1)~ và ô ~(r_i,c_i)~ thì có tất cả ~\begin{pmatrix}r_i - 1 + c_i - 1\\ r_i - 1\end{pmatrix} ~ cách để đi từ ô ~(1,1)~ đến ô ~(r_i, c_i)~. Ta có thể tính được ~dp[i]~ bằng cách trừ giá trị này cho số cách đi qua các ô vuông giữa đường đi từ ô ~(1,1)~ đến chướng ngại vật ~(r_i,c_i)~ bằng cách duyệt qua tất cả các ô ~j~ sao cho ~r_j \le r_i~ và ~c_j \le c_i~. Hay ta có:
Để có được đáp án, ta chỉ cần thêm một chướng ngại vật tại ~(H, W)~ và lấy kết quả từ mảng ~{dp}~.
Tham khảo thêm: Các kiến thức cơ bản về Tổ hợp và Nghịch đảo modulo .
Độ phức tạp: ~\mathcal O(H + W + N \log(N) + N^2)~
Code mẫu:
#include <bits/stdc++.h> using namespace std; #define Hmax 100000 #define N 3000 #define MOD 1000000007 int n, m, k, dp[N + 1]; long long fac[Hmax << 1], ifac[Hmax << 1]; struct P { int x, y; bool operator<(const P& other) const { if (x == other.x) return y < other.y; return x < other.x; } } point[N + 1]; int power(long long x, int p) { long long res = 1; while (p > 0) { if (p & 1) res = res * x % MOD; x = x * x % MOD, p >>= 1; } return res; } void genFac(int size) { fac[0] = 1; for (int i = 1; i <= size; ++i) fac[i] = fac[i - 1] * i % MOD; ifac[size] = power(fac[size], MOD - 2); for (int i = size; i >= 1; --i) ifac[i - 1] = ifac[i] * i % MOD; } int choose(int n, int k) { assert(n >= k); return fac[n] * ifac[k] % MOD * ifac[n - k] % MOD; } int path(int i, int j, int x, int y) { assert(i <= x && j <= y); return choose(x - i + y - j, x - i); } int main() { scanf("%d%d%d", &n, &m, &k); genFac(n + m - 1); for (int i = 0; i < k; ++i) scanf("%d%d", &point[i].x, &point[i].y); point[k] = {n, m}; sort(point, point + k + 1); for (int i = 0; i <= k; ++i) { long long sum = path(1, 1, point[i].x, point[i].y); for (int j = 0; j < i; ++j) if (point[i].y - point[j].y >= 0) { sum = sum - (long long) dp[j] * path(point[j].x, point[j].y, point[i].x, point[i].y) % MOD; if (sum < 0) sum += MOD; } dp[i] = sum; } printf("%d\n", dp[k]); }
Bình luận
.
công thức đó đúng mà với C(k,n) thì C(x-i,x-i+y-i) đúng nha
Mọi người ơi,ai có thể giải thích hộ em cái công thức tính số cách đi từ ô (i,j) đến ô (x,y) được không ạ.Em xin cảm ơn nhiều ạ.
Em xin góp ý chỗ này phải là ~{x-i+y-j}\choose{x-i}~ mới đúng chứ ạ.