Lời giải: Đếm số cách đi từ S đến T

Tư duy

Bản đồ thành phố đảm bảo không có vòng khép kín theo chiều đi của các con đường. Điều này có nghĩa là ta luôn có thể sắp xếp được thứ tự các địa điểm sao cho mỗi con đường đều đi từ địa điểm xuất hiện trước sang địa điểm xuất hiện sau. Lợi dụng thứ tự này, ta tính số cách đi tới từng địa điểm một cách "tích lũy".

Cách giải (Quy hoạch động theo thứ tự đảm bảo)

1. Bước 1: Sắp xếp các địa điểm theo một thứ tự đảm bảo rằng mọi con đường đều đi từ trước sang sau. Thuật toán Kahn dựa trên bán bậc vào (indeg) thực hiện điều này trong \(O(N + M)\).
2. Bước 2: Gọi dp[v] là số cách đi từ S đến v. Khởi tạo dp[S] = 1, các dp[v] còn lại bằng \(0\).

3. Bước 3: Duyệt các địa điểm theo thứ tự sap xep đảm bảo. Với mỗi địa điểm \(u\) đang xét, với mỗi con đường \(u \to v\), ta cập nhật: \[dp[v] \mathrel{+}= dp[u] \pmod{10^9 + 7}\]

   Vì mọi địa điểm "đi vào" \(v\) đều đứng trước \(v\) trong thứ tự, nên khi xét \(v\) thì dp[u] đã được tính xong.

4. Kết quả: dp[T] chính là đáp số cần tìm.

Đánh giá độ phức tạp

• Bước sắp xếp: \(O(N + M)\).
• Bước quy hoạch động: \(O(N + M)\).
• Tổng: \(O(N + M)\) thời gian, \(O(N + M)\) bộ nhớ.

Mã nguồn tham khảo (C++)

#include <bits/stdc++.h>
using namespace std;

const long long MOD = 1000000007LL;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vector<vector<int>> adj(N + 1);
    vector<int> indeg(N + 1, 0);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        indeg[v]++;
    }
    int S, T;
    cin >> S >> T;

    // Sap xep theo thu tu dam bao moi dinh truoc deu duoc xu ly truoc
    queue<int> q;
    for (int i = 1; i <= N; ++i) {
        if (indeg[i] == 0) q.push(i);
    }
    vector<int> order;
    order.reserve(N);
    while (!q.empty()) {
        int u = q.front(); q.pop();
        order.push_back(u);
        for (int v : adj[u]) {
            if (--indeg[v] == 0) q.push(v);
        }
    }

    vector<long long> dp(N + 1, 0);
    dp[S] = 1;
    for (int u : order) {
        if (dp[u] == 0 && u != S) continue;
        for (int v : adj[u]) {
            dp[v] = (dp[v] + dp[u]) % MOD;
        }
    }
    cout << dp[T] % MOD << "\n";
    return 0;
}