1434. Number of Ways to Wear Different Hats to Each Other
There are n people and 40 types of hats labeled from 1 to 40.
Given a 2D integer array hats, where hats[i] is a list of all hats preferred by the ith person.
Return the number of ways that the n people wear different hats to each other.
Since the answer may be too large, return it modulo 109 + 7.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35
| class Solution { long dp[41][1<<10]; int mod = 1e9 + 7; int allSelected = 0; int maHat = 0; long helper(int mask, unordered_map<int, vector<int>>& peoples, int hat) { if(mask == allSelected) return 1l; if(hat == maHat) return 0l; if(dp[hat][mask] != -1) return dp[hat][mask]; long& res = dp[hat][mask] = helper(mask, peoples, hat + 1); for(auto p : peoples[hat]) { if(mask & 1<<p) continue; res = (res + helper(mask | 1<<p, peoples, hat + 1)) % mod; } return res; } public: int numberWays(vector<vector<int>>& hats) { memset(dp,-1,sizeof(dp)); unordered_map<int,vector<int>> peoples; int n = hats.size(); allSelected = (1<<n) - 1; for(int i = 0; i < n; i++) { for(auto h : hats[i]) { peoples[h].push_back(i); maHat = max(maHat, h); } } maHat += 1; return helper(0,peoples,1); } };
|