Độ phức tạp thời gian: ~O(N*2^N)~

Chúng ta định nghĩa ~dp[S]~ là số cách để ghép những người trong tập ~S~ vào ~|S|~ người đàn ông đầu tiên, từ đó ta có công thức như sau: ~ dp[S] = \sum dp[S/x] : a[|S|][x] = 1~

(Dấu : ở đây nghĩa là "thỏa mãn điều kiện")

(~S/x~ nghĩa là tập ~S~ bỏ phần tử ~x~)

Lưu ý: các tập S có thể được biểu diễn dưới dạng chuỗi nhị phân có ~2^N~ bit (bitmask).

Có thể giải thích công thức trên như sau: Số cách ghép cho tập ~S~ mà trong đó có người phụ nữ ~x~ nào đó sẽ là tổng tất cả các cách ghép không có người phụ nữ ~x~ và người phụ nữ ~x~ và người đàn ông ~|S|~ phải hợp nhau.

Base case của chúng ta là tập rỗng, có giá trị bằng ~1~ (tập rỗng có thể được tính là một cách ghép duy nhất có ~0~ cặp).

Code

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;
const int MAX_N = 21;

bool compat[MAX_N][MAX_N];
int dp[1 << MAX_N];

int main() {
    int N;
    cin >> N;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            cin >> compat[i][j];
        }
    }

    dp[0] = 1;

    for (int s = 0; s < (1 << N); s++) {
        int pair_num = __builtin_popcount(s); // the number of 1-bit in number s
        for (int w = 0; w < N; w++) {
            /*
             * check that
             * 1. this woman hasn't been paired already
             * 2. she's also compatible with the {pair_num + 1}th man
             */
            if ((s & (1 << w)) || !compat[pair_num][w])
                continue;

            // add the amount to future dp states
            dp[s | (1 << w)] += dp[s];
            dp[s | (1 << w)] %= MOD;
        }
    }

    cout << dp[(1 << N) - 1] << endl;
}