จำนวนวิธีสวมหมวกต่างกันแต่ละคนใน C++

ปัญหา

มีคน n คน และหมวก 40 ประเภท (เลข 1-40) แต่ละคนมีรายการหมวกที่ชอบ (2D list hats) หาจำนวนวิธีที่คนทุกคนสวมหมวกต่างกันหมด (ไม่มีใครสวมหมวกซ้ำ) คำตอบ modulo 10^9 + 7

ตัวอย่าง: hats = [[4,6,2],[4,6]] → 4 วิธี: [4,6], [6,4], [2,4], [2,6]

แนวคิด: DP + Bitmask + Hat-to-People Mapping

แทนที่จะวนคน เรา วนหมวก (1..40) เพราะหมวกน้อยกว่าคน (40 vs n≤10)

State

• dp[hat_id][mask] = จำนวนวิธีแจกหมวก 1..hat_id ให้คนใน mask (bit i = 1 หมายถึงคน i ได้หมวกแล้ว)
• mask ขนาด 2^n (n ≤ 10 → 1024 states)

Transition

ที่หมวก hat_id:

1. ไม่แจกหมวกนี้: dp[hat_id][mask] += dp[hat_id+1][mask]
2. แจกให้คน i ที่ชอบหมวกนี้ และยังไม่มีหมวก: ถ้า mask & (1<<i) == 0 แล้ว dp[hat_id][mask] += dp[hat_id+1][mask | (1<<i)]

Base Case

• mask == (1<<n)-1 (ทุกคนมีหมวกครบ) → return 1
• hat_id == 41 (หมวกหมดแล้ว) → return 0

โค้ด C++

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

int dp[55][1 << 11];  // hat_id up to 40, mask up to 2^10

class Solution {
    vector<vector<int>> hat_to_people;  // hat_id -> list of people who like it
    int target_mask;
    
    int add(lli a, lli b) {
        return ((a % MOD) + (b % MOD)) % MOD;
    }
    
    int solve(int hat_id, int mask) {
        if (mask == target_mask) return 1;
        if (hat_id == 41) return 0;
        if (dp[hat_id][mask] != -1) return dp[hat_id][mask];
        
        int ret = solve(hat_id + 1, mask);  // ไม่แจกหมวกนี้
        
        for (int person : hat_to_people[hat_id]) {
            if (!(mask & (1 << person))) {  // คนนี้ยังไม่มีหมวก
                ret = add(ret, solve(hat_id + 1, mask | (1 << person)));
            }
        }
        
        return dp[hat_id][mask] = ret;
    }
    
public:
    int numberWays(vector<vector<int>>& hats) {
        memset(dp, -1, sizeof(dp));
        int n = hats.size();
        hat_to_people.assign(50, {});  // 1..40
        
        // สร้าง mapping: หมวก -> คนที่ชอบ
        for (int i = 0; i < n; i++) {
            for (int hat : hats[i]) {
                hat_to_people[hat].push_back(i);
            }
        }
        
        target_mask = (1 << n) - 1;
        return solve(1, 0);  // เริ่มจากหมวก 1, mask=0
    }
};

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

ความซับซ้อน

• Time: O(40 × 2^n × n) ≈ 40 × 1024 × 10 = ~400K operations
• Space: O(40 × 2^n) ≈ 40KB

Input / Output

Input:  [[4,6,2],[4,6]]
Output: 4