Bổ đề LGV (Lindström-Gessel-Viennot)
Đếm họ đường đi không giao nhau trên DAG hoặc lưới bằng định thức của ma trận số đường đi: chứng minh bằng phép đổi đuôi, ví dụ lưới có vật cản, cài đặt định thức modulo bằng khử Gauss và liên hệ với bảng Young, phân hoạch phẳng, số Catalan.
Bổ đề Lindström-Gessel-Viennot (gọi tắt LGV) biến bài toán đếm họ đường đi không giao nhau trên một đồ thị có hướng không chu trình (DAG) thành việc tính một định thức . Mỗi phần tử của ma trận chỉ là số đường đi từ một điểm xuất phát tới một điểm đích, tính bằng quy hoạch động thông thường. Thay vì quy hoạch động trên trạng thái gồm vị trí của cả đường (cỡ trạng thái trên lưới ), ta chỉ cần cho các số đường đi cộng cho định thức bằng khử Gauss.
Dạng bài kinh điển: "đếm số cặp đường đi từ góc trái trên tới góc phải dưới, chỉ đi sang phải hoặc xuống, không có ô chung ngoài hai đầu mút" trên lưới có vật cản. Đáp án là với là số đường đi đơn lẻ.
Phát biểu
Cho DAG (mỗi cạnh có thể có trọng số, trọng số của một đường đi là tích trọng số các cạnh; đếm thuần thì mọi trọng số bằng ). Chọn đỉnh xuất phát và đỉnh đích . Đặt
Khi đó
trong đó tổng chạy trên mọi bộ đường đi đôi một không chung đỉnh (vertex-disjoint) với đi từ tới , là một hoán vị.
Hệ quả dùng nhiều nhất. Nếu với mọi hoán vị không tồn tại bộ đường đi rời nhau nào nối , thì đúng bằng số (tổng trọng số) họ đường đi rời nhau nối .
Ý tưởng / Trực giác
Khai triển định thức. Theo định nghĩa,
tức là tổng có dấu trên mọi cặp (hoán vị , bộ đường ), kể cả các bộ có đường cắt nhau. Ta cần chứng minh phần đóng góp của các bộ có giao nhau triệt tiêu hết.
Phép đổi đuôi (tail swapping). Với một bộ có giao nhau, chọn theo một quy tắc cố định:
- là chỉ số nhỏ nhất sao cho chung đỉnh với một đường khác;
- là đỉnh đầu tiên trên (tính từ ) nằm trên một đường khác;
- là chỉ số nhỏ nhất khác sao cho đi qua .
Đổi phần đuôi sau của và : giữ đoạn rồi đi tiếp theo đuôi của , và ngược lại. Bộ mới:
- có cùng tích trọng số (vẫn là đúng những cạnh đó, chỉ chia lại cho hai đường);
- có hoán vị , nên dấu đổi ngược;
- vẫn có giao nhau, và áp dụng lại quy tắc thì chọn đúng cũ (đoạn không đổi, và vì không có chu trình nên đoạn đó không thể gặp đuôi mới), nên đổi đuôi lần nữa trả về bộ ban đầu.
Như vậy các bộ có giao nhau được ghép thành từng cặp cùng trọng số, ngược dấu, và cộng lại bằng . Chỉ còn lại các bộ rời nhau. Đây là cùng một ý tưởng với nguyên lý phản xạ khi đếm đường đi không chạm một đường thẳng: mỗi đường "xấu" được ghép với một đường bị đổi điểm xuất phát, và ta trừ đi.
Khi nào chỉ còn hoán vị đơn vị? Điều kiện thường gặp là tính phẳng: vẽ được trên mặt phẳng, các và nằm trên biên theo thứ tự (đi vòng quanh biên). Khi đó đường và (với ) buộc phải cắt nhau, và trên lưới chỉ đi sang phải hoặc xuống thì "cắt nhau" nghĩa là có ô chung (hai đường như vậy không thể bắt chéo mà không đứng chung một ô). Do đó mọi đều có một nghịch thế , , buộc hai đường giao nhau, và đóng góp .
Ví dụ chạy tay
Lưới , đi sang phải hoặc xuống. Đếm số cặp đường từ ô tới ô không có ô chung ngoài hai đầu mút. Bỏ hai đầu mút chung: đường "trên" phải đi , đường "dưới" đi . Vậy đặt
grid .... .... .... .... label 1,2 A1 label 2,1 A2 label 3,4 B1 label 4,3 B2 step Một cặp đường rời nhau: A1 → B1 và A2 → B2 path blue 1,2 1,3 1,4 2,4 3,4 path green 2,1 3,1 4,1 4,2 4,3 step Một cặp có giao nhau: chung ô (2,2) và (3,2) clear path blue 1,2 2,2 3,2 3,3 3,4 path green 2,1 2,2 3,2 4,2 4,3 highlight red 2,2 step Đổi đuôi tại ô chung đầu tiên (2,2): giờ A1 → B2 và A2 → B1, dấu đổi ngược clear path blue 1,2 2,2 3,2 4,2 4,3 path green 2,1 2,2 3,2 3,3 3,4 highlight red 2,2
Không có vật cản, số đường từ tới là :
| xuống , phải : | xuống , phải : | |
| xuống , phải : | xuống , phải : |
Ý nghĩa: trong cặp có cặp giao nhau, và phép đổi đuôi biến chúng một-một thành cặp (cặp kiểu này luôn giao nhau). Còn lại cặp rời nhau; vét cạn trực tiếp cặp đường cũng ra .
Thêm vật cản ở ô . Số đường tránh vật cản = tổng số đường trừ số đường đi qua :
- : ;
- : ;
- : ;
- : .
grid .... ..#. .... .... label 1,2 A1 label 2,1 A2 label 3,4 B1 label 4,3 B2
Chương trình bên dưới in đúng hai ma trận này và các định thức , . Với trên lưới trống , , , ma trận là và định thức là , khớp với vét cạn.
Cài đặt
Đầu vào: , lưới (. là ô trống, # là vật cản), số đường , rồi ô xuất phát và ô đích (đánh số từ ). Chương trình tính ma trận số đường đi bằng quy hoạch động (một lượt cho mỗi điểm xuất phát), in ma trận và định thức modulo bằng khử Gauss.
Ví dụ đầu vào cho lưới trống ở trên:
4 4
....
....
....
....
2
1 2
2 1
3 4
4 3
Đầu ra:
6 4
4 6
20
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9 + 7;
long long power(long long a, long long b) {
long long res = 1;
a %= MOD;
for (; b > 0; b >>= 1) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
}
return res;
}
// Determinant modulo a prime by Gaussian elimination, O(k^3)
long long det_mod(vector<vector<long long>> a) {
int k = a.size();
long long det = 1;
for (int col = 0; col < k; col++) {
int piv = -1;
for (int r = col; r < k; r++)
if (a[r][col] != 0) { piv = r; break; }
if (piv == -1) return 0; // singular matrix
if (piv != col) {
swap(a[piv], a[col]);
det = (MOD - det) % MOD; // a row swap flips the sign
}
det = det * a[col][col] % MOD;
long long inv = power(a[col][col], MOD - 2);
for (int r = col + 1; r < k; r++) {
long long f = a[r][col] * inv % MOD;
if (f == 0) continue;
for (int c = col; c < k; c++)
a[r][c] = ((a[r][c] - f * a[col][c]) % MOD + MOD) % MOD;
}
}
return det;
}
int main() {
int n, m;
cin >> n >> m;
vector<string> g(n);
for (auto& row : g) cin >> row;
int k;
cin >> k;
vector<pair<int, int>> src(k), dst(k);
for (auto& [r, c] : src) { cin >> r >> c; r--; c--; }
for (auto& [r, c] : dst) { cin >> r >> c; r--; c--; }
// M[i][j] = number of right/down paths from src[i] to dst[j] avoiding '#'
vector<vector<long long>> M(k, vector<long long>(k, 0));
for (int i = 0; i < k; i++) {
vector<vector<long long>> f(n, vector<long long>(m, 0));
auto [sr, sc] = src[i];
if (g[sr][sc] != '#') f[sr][sc] = 1;
for (int r = sr; r < n; r++)
for (int c = sc; c < m; c++) {
if (g[r][c] == '#') { f[r][c] = 0; continue; }
if (r > sr) f[r][c] += f[r - 1][c];
if (c > sc) f[r][c] += f[r][c - 1];
f[r][c] %= MOD;
}
for (int j = 0; j < k; j++) {
auto [tr, tc] = dst[j];
if (tr >= sr && tc >= sc) M[i][j] = f[tr][tc];
}
}
for (int i = 0; i < k; i++)
for (int j = 0; j < k; j++) cout << M[i][j] << (j + 1 < k ? ' ' : '\n');
cout << det_mod(M) << '\n';
}
import sys
MOD = 10**9 + 7
# Determinant modulo a prime by Gaussian elimination, O(k^3)
def det_mod(a):
a = [row[:] for row in a]
k = len(a)
det = 1
for col in range(k):
piv = next((r for r in range(col, k) if a[r][col]), -1)
if piv == -1:
return 0 # singular matrix
if piv != col:
a[piv], a[col] = a[col], a[piv]
det = -det % MOD # a row swap flips the sign
det = det * a[col][col] % MOD
inv = pow(a[col][col], MOD - 2, MOD)
for r in range(col + 1, k):
f = a[r][col] * inv % MOD
if f:
for c in range(col, k):
a[r][c] = (a[r][c] - f * a[col][c]) % MOD
return det
def main():
data = sys.stdin.read().split()
n, m = int(data[0]), int(data[1])
g = data[2:2 + n]
pos = 2 + n
k = int(data[pos]); pos += 1
pts = [(int(data[pos + 2 * i]) - 1, int(data[pos + 2 * i + 1]) - 1) for i in range(2 * k)]
src, dst = pts[:k], pts[k:]
# M[i][j] = number of right/down paths from src[i] to dst[j] avoiding '#'
M = [[0] * k for _ in range(k)]
for i, (sr, sc) in enumerate(src):
f = [[0] * m for _ in range(n)]
for r in range(sr, n):
for c in range(sc, m):
if g[r][c] == '#':
continue
if r == sr and c == sc:
f[r][c] = 1
continue
v = (f[r - 1][c] if r > sr else 0) + (f[r][c - 1] if c > sc else 0)
f[r][c] = v % MOD
for j, (tr, tc) in enumerate(dst):
if tr >= sr and tc >= sc:
M[i][j] = f[tr][tc]
out = [" ".join(map(str, row)) for row in M]
out.append(str(det_mod(M)))
print("\n".join(out))
main()
Kiểm chứng. Cả hai chương trình được so với một chương trình vét cạn (liệt kê mọi bộ đường đi, giữ các bộ đôi một không chung ô, cộng theo dấu của hoán vị) trên lưới ngẫu nhiên tới , , có vật cản, với điểm xuất phát và đích bất kỳ: định thức luôn bằng tổng có dấu, đúng như bổ đề phát biểu (kể cả khi có hoán vị khác đơn vị đóng góp).
Trên DAG tổng quát, thay quy hoạch động lưới bằng quy hoạch động theo thứ tự tô-pô: , (xem Quy hoạch động trên đồ thị).
Độ phức tạp
| Bước | Thời gian | Bộ nhớ |
|---|---|---|
| Ma trận số đường đi trên lưới | ||
| Ma trận số đường đi trên DAG đỉnh, cạnh | ||
| Định thức modulo nguyên tố bằng khử Gauss |
Vì sao? Mỗi điểm xuất phát cần đúng một lượt quy hoạch động để biết số đường tới mọi điểm đích cùng lúc, nên chỉ lượt chứ không phải . Khử Gauss có cột, mỗi cột khử hàng, mỗi hàng phép tính, cộng một lần nghịch đảo modulo cho mỗi phần tử trụ. So với quy hoạch động trực tiếp trên vị trí của cả đường (với đã là trạng thái theo đường chéo, và tăng theo hàm mũ với ), LGV gần như "miễn phí" sau phần đếm đường đơn lẻ.
⚠️ Lỗi thường gặp
- Quên dịch hai đầu mút chung. Nếu hai đường cùng xuất phát ở và cùng kết thúc ở , đặt thì hai hàng của ma trận bằng nhau và định thức luôn là . Phải dịch sang , , , . Nhớ kiểm tra các ô này không phải vật cản (nếu là vật cản thì hàng hoặc cột tương ứng bằng , đáp án là đúng).
- Áp dụng khi hoán vị khác đơn vị vẫn có họ rời nhau. LGV luôn cho tổng có dấu. Nếu nguồn và đích không nằm "cùng thứ tự" (ví dụ trên lưới, ở bên phải nhưng lại ở bên trái , hoặc đồ thị không phẳng), không phải là số cách. Triệu chứng: đáp án âm hoặc nhỏ vô lý. Cách tránh: sắp các nguồn và các đích cùng một chiều (ví dụ theo đường chéo), và tự hỏi "hai đường , có buộc phải chung ô không?".
- Đổi thứ tự hàng hoặc cột tùy tiện. Hoán đổi hai hàng (hoặc hai cột) đổi dấu định thức. Nếu sắp nguồn theo một thứ tự và đích theo thứ tự ngược lại, kết quả modulo trở thành . Luôn ghép với là cặp được nối trong họ "đúng".
- Khử Gauss bằng số thực hoặc chia nguyên. Số đường đi rất lớn nên phải làm modulo; khi phần tử trụ bằng modulo phải tìm hàng khác để đổi chỗ (và đổi dấu), không được dừng sớm. Nếu modulo không nguyên tố thì không có nghịch đảo, phải khử kiểu thuật toán Euclid trên hai hàng (xem Khử Gauss).
- Hiểu "không giao nhau" là không chung cạnh. LGV đếm họ đường không chung đỉnh. Nếu đề chỉ cấm chung cạnh (cho phép chạm nhau tại một đỉnh) thì không dùng trực tiếp được; với lưới ô vuông, đề "không chung ô" chính là không chung đỉnh trên đồ thị các ô.
- Đếm có thứ tự hay không thứ tự. Với hai đường từ cùng một góc, LGV đếm mỗi cặp đúng một lần. Nếu đề coi hai người khác nhau (người đi trên hoặc đi dưới) thì nhân .
Biến thể / Mở rộng
- Có trọng số. Gán trọng số cho cạnh hoặc ô (ví dụ cho mỗi bước sang phải), cho đa thức sinh của các họ rời nhau theo tổng trọng số. Dùng được với hàm sinh hoặc tính tại nhiều điểm rồi nội suy.
- Bảng Young nửa chuẩn (công thức Jacobi-Trudi). Số bảng Young nửa chuẩn hình với giá trị trong bằng mỗi hàng của bảng được mã hóa thành một đường đi trên lưới, và điều kiện "cột tăng ngặt" đúng là các đường không giao nhau. Ví dụ , : , khớp công thức móc-nội dung. Xem Young tableau và công thức móc.
- Phân hoạch phẳng (plane partition). Số phân hoạch phẳng nằm trong hộp (tương đương số cách lát hình lục giác bằng hình thoi) bằng và bằng công thức MacMahon . Với ta được đúng ma trận của ví dụ trên, định thức .
- Số Catalan và định thức Hankel. Đường Dyck là đường đi trên lưới không xuống dưới trục hoành; LGV cho (ví dụ : ), vì chỉ có đúng một họ đường Dyck rời nhau. Cặp đường như ví dụ trên trong hộp được đếm bởi số Narayana; xem Tổ hợp.
- Nguyên lý phản xạ và bao hàm loại trừ. Với và một "bức tường" (đường thẳng cấm chạm), ý tưởng ghép cặp triệt tiêu dấu chính là nguyên lý phản xạ; nhiều bức tường cho tổng bao hàm loại trừ trên các ảnh phản xạ (xem Bao hàm loại trừ). Các hạt không vượt nhau trên một vòng tròn dẫn tới phản xạ theo nhóm affine, gộp lại cũng thành một định thức.
- Nhiều điểm xuất phát, ít ràng buộc ở đích. Khi lớn (vài trăm) và lưới nhỏ, thời gian chủ yếu nằm ở lượt quy hoạch động; khi các điểm đích nằm trên một đường chéo và lưới không có vật cản, mỗi phần tử là một tổ hợp tính sau khi có giai thừa.
Bài tập luyện
Kho bài hiện chưa có bài "đếm cặp đường không giao nhau trên lưới" thuần LGV; các bài dưới đây luyện từng thành phần của kỹ thuật và các bài nâng cao dùng định thức của ma trận đường đi.
- Đường Đi Trên Lưới (gridpath1): (Dễ) Đếm đường đi sang phải hoặc xuống trên lưới có bẫy, modulo . Đây chính là quy hoạch động để tính mỗi phần tử của ma trận.
- Xếp kệ hợp lệ (vtc08_bracket): (Rất khó) Đếm đường đi không chạm hai bức tường bằng nguyên lý phản xạ lặp: phiên bản một đường của phép ghép cặp triệt tiêu dấu trong chứng minh LGV.
- Sơ đồ Định Tuyến (routschemes): (Chuyên gia) Loại các cách ghép tạo chu trình qua tối đa hai cạnh ngược; bao hàm loại trừ được gói gọn thành định thức với là ma trận tổng trọng số đường đi giữa các đầu mút cạnh ngược.
- Ống dẫn quỹ đạo kín (icpc26mbg): (Bậc thầy) hộp không vượt nhau trên vòng tròn là đường đi không giao nhau; phản xạ có trọng số theo nhóm affine rút gọn về hệ số tự do của một định thức đa thức , tính bằng NTT và khử Gauss.
Bình luận