Mô tả bài toán

Cho \(N\) bạn nam và \(N\) bạn nữ, được đánh số từ \(1\) đến \(N\). Mỗi cặp \((i, j)\) tương ứng với bạn nam \(i\) và bạn nữ \(j\) có độ hợp nhau \(a_{i,j}\), trong đó:

• \(a_{i,j} = 1\): hai bạn hợp nhau.
• \(a_{i,j} = 0\): hai bạn không hợp nhau.

Yêu cầu: Tìm số cách chia \(N\) cặp gồm mỗi bạn nam và một bạn nữ sao cho mỗi cặp đã ghép là hợp nhau.

In ra kết quả modulo \(10^9 + 7\).

Ý tưởng giải

Sử dụng quy hoạch động với Bitmask:

• Gọi \(dp[mask]\) là số cách để ghép khi đã chọn một tập hợp các bạn nữ theo bitmask.
• Số bit 1 trong mask chính là số bạn nam đã ghép. Ta gọi là \(i\).
• Từ mask hiện tại, ta xét các bạn nữ chưa được chọn (bit = 0), và xem bạn nam \(i\) có hợp với bạn nữ \(j\) hay không.

Công thức quy hoạch động:

\[ dp[mask\ |\ (1 \ll j)] += dp[mask] \ (mod\ 10^9+7) \]

Với điều kiện: \(a[i][j] = 1\) và bit j trong mask đang bằng 0.

Minh họa

Input:

3
0 1 1
1 0 1
1 1 1

Output:

3

Giải thích: 3 cách ghép hợp lệ:

• (1,2); (2,1); (3,3)
• (1,2); (2,3); (3,1)
• (1,3); (2,1); (3,2)

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

• Số trạng thái mask tối đa: \(2^N\)
• Với mỗi mask duyệt tối đa \(N\) bạn nữ.
• Độ phức tạp: \(O(N \cdot 2^N)\), chấp nhận được với \(N \leq 21\)

Code minh họa (C++)

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

const long long 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);
        if (i >= N) continue;
        for (int j = 0; j < N; j++){
            if (!(mask & (1 << j)) && a[i][j] == 1) {
                dp[mask | (1 << j)] = (dp[mask | (1 << j)] + dp[mask]) % MOD;
            }
        }
    }

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