Number of Ways to Wear Different Hats to Each Other trong C++

Có n người và 40 loại mũ (1-40). hats[i] = danh sách mũ người i thích. Tìm số cách phân mũ sao cho mỗi người được 1 mũ khác nhau, mỗi mũ tối đa 1 người. Kết quả modulo 10^9+7.

Ví dụ: [[4,6,2],[4,6]] → 4 cách: [4,6], [6,4], [2,4], [2,6].

Giải thuật (DP + Bitmask)

DP[hat][mask] = số cách phân mũ từ hat..40 với mask người đã có mũ. Chuyển đổi: không dùng hat này, hoặc gán hat cho một người chưa có mũ và thích hat này.

Ví dụ triển khai C++

#include <bits/stdc++.h>
using namespace std;
typedef long long lli;
const int MOD = 1e9 + 7;
int dp[55][1 << 11];

class Solution {
    vector<vector<int>> hatToPeople;
    int n, fullMask;
    
    int add(lli a, lli b) { return (a + b) % MOD; }
    
    int solve(int hat, int mask) {
        if (mask == fullMask) return 1;
        if (hat > 40) return 0;
        if (dp[hat][mask] != -1) return dp[hat][mask];
        
        int res = solve(hat + 1, mask); // không dùng mũ này
        for (int person : hatToPeople[hat]) {
            if (!(mask & (1 << person))) {
                res = add(res, solve(hat + 1, mask | (1 << person)));
            }
        }
        return dp[hat][mask] = res;
    }
    
public:
    int numberWays(vector<vector<int>>& hats) {
        memset(dp, -1, sizeof(dp));
        n = hats.size();
        hatToPeople.assign(41, {});
        for (int i = 0; i < n; i++)
            for (int h : hats[i])
                hatToPeople[h].push_back(i);
        fullMask = (1 << n) - 1;
        return solve(1, 0);
    }
};

int main() {
    Solution ob;
    vector<vector<int>> v = {{4,6,2},{4,6}};
    cout << ob.numberWays(v); // 4
    return 0;
}

Đầu vào / Đầu ra

Input: {{4,6,2},{4,6}}
Output: 4