Lời giải: Đếm số cách đi từ S đến T đúng K bước

Tư duy

Bài toán yêu cầu đếm số đường đi (không nhất thiết phải qua ít bước nhất) từ \(S\) đến \(T\) có đúng \(K\) cạnh. Vì bản đồ đảm bảo không có vòng khép kín, mỗi đường đi sử dụng một đỉnh tối đa một lần, nên số bước nhảy chính là số đỉnh trừ \(1\).

Với \(K \le 100\) và \(N \le 5 \cdot 10^3\), ta có thể dùng quy hoạch động 2 chiều: trạng thái là cặp (đỉnh hiện tại, số bước đã đi).

Cách giải (DP 2D theo thứ tự đảm bảo)

1. Bước 1: Sắp xếp các địa điểm theo thứ tự đảm bảo (topo sort Kahn) trong \(O(N + M)\).
2. Bước 2: Gọi dp[v][k] là số cách đi từ \(S\) đến \(v\) đúng \(k\) bước (tức là \(k\) con đường). Khởi tạo dp[S][0] = 1, các giá trị khác bằng \(0\).
3. Bước 3: Duyệt theo thứ tự đảm bảo. Với mỗi địa điểm \(u\), với mỗi \(k \in [1, K]\), với mỗi con đường \(u \to v\): \[dp[v][k] = \left(\,dp[v][k] + dp[u][k-1]\,\right) \bmod 10^9 + 7\]
4. Kết quả: dp[T][K] là đáp số cần tìm.

Tại sao thuật toán đúng?

• Thứ tự đảm bảo đảm bảo mọi đỉnh "trước \(u\)" đều đã được xử lý, nên khi xét \(u\), các giá trị dp[u][*] đã đúng.
• Truy hồi dp[v][k] = sum_{u→v} dp[u][k-1] đếm đúng số cách đến \(v\) đúng \(k\) bước: bước cuối cùng phải đi qua một cạnh \(u \to v\) nào đó, và phần đầu của đường đi phải là một đường đi đúng \(k-1\) bước đến \(u\).
• Đáp án đúng là dp[T][K].

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

• Bộ nhớ: \(O(N \cdot K)\) trạng thái.
• Sắp xếp: \(O(N + M)\).
• Quy hoạch động: \(O(K \cdot M)\) (vì mỗi cạnh được cập nhật \(K\) lần).
• Tổng: \(O(N + M + K \cdot M)\) thời gian, \(O(N \cdot K)\) 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, K;
    cin >> S >> T >> K;

    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<vector<long long>> dp(N + 1, vector<long long>(K + 1, 0));
    dp[S][0] = 1;
    for (int u : order) {
        for (int k = 1; k <= K; ++k) {
            if (dp[u][k - 1] == 0) continue;
            for (int v : adj[u]) {
                dp[v][k] = (dp[v][k] + dp[u][k - 1]) % MOD;
            }
        }
    }
    cout << dp[T][K] % MOD << "\n";
    return 0;
}