Hiểu bài toán

Bài toán yêu cầu tìm số cách tạo N cặp (đàn ông, phụ nữ) sao cho mỗi người chỉ thuộc đúng 1 cặp và độ 'hợp nhau' (a_{ij} = 1). Đây là bài toán đếm số cách ghép đôi hoàn hảo (Perfect Matching) trong đồ thị hai phía N-N, hay chính là bài toán Tính chất vế (Permanent) của ma trận 0-1. Với N ≤ 21, ta cần một thuật toán hiệu quả.

Các cách tiếp cận

Cách Quy hoạch động theo tập hợp (DP on Subsets)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000007;

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

    int N;
    cin >> N;
    vector<vector<int>> a(N, vector<int>(N));
    for(int i=0;i<N;i++) for(int j=0;j<N;j++) cin >> a[i][j];

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

    for(int mask = 0; mask < (1<<N); mask++){
        int i = __builtin_popcount(mask);
        for(int j = 0; j < N; j++){
            if(!(mask & (1<<j)) && a[i][j]){
                dp[mask | (1<<j)] = (dp[mask | (1<<j)] + dp[mask]) % MOD;
            }
        }
    }

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

• Time Complexity: O(N * 2^N)
• Space Complexity: O(2^N)

Đây là cách tiếp cận chuẩn cho bài toán ghép đôi/N queens. Ta coi dp[mask] là số cách ghép đôi cho các cô gái đánh dấu trong bitset 'mask'. Để chuyển từ state mask sang state mask | (1<<j), ta cần kiểm tra xem cô gái j có hợp với người đàn ông thứ i (tức là 'popcount(mask)') hay không. Vòng lặp chạy qua tất cả các mask từ 0 đến 2^N - 1. Với mỗi mask, ta biết genau có bao nhiêu cô gái đã được chọn (i), và người đàn ông tiếp theo (thứ i) sẽ chọn cô gái j chưa được chọn. Độ phức tạp là O(N * 2^N) vì có 2^N states và mỗi state duyệt qua N cô gái.</p>

Cách Quy hoạch động tối ưu (Cùng logic, code tham khảo)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;

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

    int N;
    cin >> N;
    vector<vector<int>> a(N, vector<int>(N));
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            cin >> a[i][j];

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

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

    cout << dp[(1<<N)-1] << "\n";
}

• Time Complexity: O(N * 2^N)
• Space Complexity: O(2^N)

Giải thuật tương tự Approach 1. Biến 'i' đại diện cho người đàn ông thứ i đang được ghép đôi. 'mask' đại diện cho tập hợp các cô gái đã được chọn. Nếu số lượng bit trong mask (popcount) đã bằng N thì bỏ qua (dù không cần thiết lắm vì dp[N] không cập nhật tiếp). Logic chính là: dp[mask | (1<<j)] += dp[mask] nếu a[i][j] == 1. Đây là cách hiệu quả nhất để giải quyết bài toán này với N nhỏ.</p>

Cách Brute Force (Đệ quy toàn bộ)

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1e9+7;
int N;
int a[25][25];
int used_women = 0;
long long ans = 0;

void solve(int man) {
    if (man == N) {
        ans = (ans + 1) % MOD;
        return;
    }
    for (int woman = 0; woman < N; woman++) {
        if (!(used_women & (1 << woman)) && a[man][woman]) {
            used_women |= (1 << woman);
            solve(man + 1);
            used_women &= ~(1 << woman);
        }
    }
}

int main() {
    cin >> N;
    for(int i=0; i<N; i++)
        for(int j=0; j<N; j++)
            cin >> a[i][j];
    solve(0);
    cout << ans;
    return 0;
}

• Time Complexity: O(N!)
• Space Complexity: O(N)

Đây là thuật toán ngẫu nhiên/tham lam(không tối ưu). Nó thử tất cả các cách sắp xếp phụ nữ cho đàn ông. Hàm solve(man) thử mọi phụ nữ chưa được chọn cho đàn ông 'man'. Nếu chọn được một người hợp lệ, đánh dấu và đệ quy cho đàn ông tiếp theo. Nếu tất cả đàn ông đều được ghép đôi, tăng biến đếm. Độ phức tạp thời gian là N! (N giai thừa), chỉ khả thi với N rất nhỏ (ví dụ N ≤ 10). Với N=21, TLE (Time Limit Exceeded).

Phân tích độ phức tạp

Bài học kinh nghiệm

• Bài toán là đếm số Perfect Matching trong đồ thị hai phía, tương đương với bài toán Tính chất vế (Permanent) của ma trận 0-1.
• Cách tiếp cận hiệu quả nhất với N ≤ 21 là Quy hoạch động theo tập hợp con (DP on Subsets) với độ phức tạp O(N * 2^N).
• Sử dụng bitmask (số nhị phân) để lưu trạng thái: 1 bit đại diện cho 1 người phụ nữ đã được chọn hay chưa.
• _builtinpopcount(mask) cho biết số lượng bit 1 trong mask, từ đó suy ra người đàn ông thứ i đang được ghép đôi.

Lỗi thường gặp

• Quên xử lý modulo 10^9+7 khi cộng dồn kết quả trong DP, dễ导致 overflow với N lớn.
• Sử dụng thuật toán O(N!) sẽ bị quá thời gian chấp nhận (TLE) với N=21.
• Lỗi truy cập mảng: a[i][j] trong khi i là số lượng người đã được chọn (popcount), j là index phụ nữ.