Lời giải: Đếm số thứ tự học thỏa ràng buộc tiên quyết

Tư duy

Bài toán yêu cầu đếm số hoán vị của \(N\) môn sao cho nếu \(u\) là tiên quyết của \(v\) thì \(u\) phải đứng trước \(v\). Đây chính là bài toán đếm số linear extension (mở rộng tuyến tính) của một thứ tự bộ phận.

Vì \(N \le 20\), ta có thể áp dụng quy hoạch động trên tập con (Subset DP) với trạng thái là một bitmask \(2^N\).

Cách giải (Subset DP)

1. Bước 1: Với mỗi môn \(v\), đặt prereq[v] là bitmask các môn là tiên quyết của \(v\) (nếu \(u\) là tiên quyết của \(v\) thì bit thứ \(u\) của mask là \(1\)). \(N \le 20\) nên bitmask vừa với một số nguyên \(64\) bit.
2. Bước 2: Gọi dp[mask] là số cách xếp thứ tự để học xong đúng các môn trong mask (thỏa tiên quyết). Khởi tạo dp[0] = 1 (chưa học môn nào, có đúng \(1\) cách).
3. Bước 3: Quy hoạch động: với mỗi mask đã biết dp[mask], ta tìm mọi môn \(i\) chưa học (bit \(i\) chưa bật trong mask) mà tất cả tiên quyết của \(i\) đều đã thuộc mask, rồi cập nhật: \[dp[mask \cup \{i\}]\ \mathrel{+}\!\!=\ dp[mask]\] Hai vế đều lấy modulo \(10^9 + 7\).
4. Kết quả: dp[(1 << N) - 1] là đáp số cần tìm (đã học đủ cả \(N\) môn).

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

• "Chưa học & tất cả tiên quyết đã thuộc mask" chính là điều kiện để có thể chọn môn \(i\) làm môn học tiếp theo. Vì tập tiên quyết đảm bảo không tạo vòng khép kín, điều kiện này luôn khả thi với một số \(i\).
• Mỗi thứ tự học hợp lệ tương ứng một-một với một chuỗi cập nhật mask từ \(0\) lên (1<<N)-1, do đó hệ thức truy hồi đếm đúng số cách.

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

• Số trạng thái: \(2^N \le 2^{20} \approx 10^6\).
• Với mỗi trạng thái, ta xét \(N\) môn → \(O(N \cdot 2^N)\).
• Tổng: \(O(N \cdot 2^N)\) thời gian, \(O(2^N)\) 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<int> mask_prereq(N, 0);
    for (int i = 0; i < M; ++i) {
        int u, v;
        cin >> u >> v;
        --u; --v;
        mask_prereq[v] |= (1 << u);
    }

    vector<long long> dp(1 << N, 0);
    dp[0] = 1;

    for (int mask = 0; mask < (1 << N); ++mask) {
        if (dp[mask] == 0) continue;
        for (int i = 0; i < N; ++i) {
            if ((mask >> i) & 1) continue;
            int req = mask_prereq[i];
            if ((mask & req) != req) continue;
            int nmask = mask | (1 << i);
            dp[nmask] = (dp[nmask] + dp[mask]) % MOD;
        }
    }

    cout << dp[(1 << N) - 1] % MOD << "\n";
    return 0;
}