n জন মানুষ এবং ৪০ ধরণের টুপি (১ থেকে ৪০) আছে। hats[i] = i-তম ব্যক্তির পছন্দের টুপি লিস্ট। প্রতিটি ব্যক্তি আলাদা টুপি পরবে এমন কতটি উপায় আছে তা বের করুন। মডুলো ১০^৯+৭।
উদাহরণ: [[4,6,2],[4,6]] -> ৪ উপায়: [4,6], [6,4], [2,4], [2,6]।
সমাধানের ধাপসমূহ
- m = 1e9+7। DP টেবিল dp[55][2^11] (ম্যাক্স ১০ জন)।
- v[hat] = পছন্দকারী ব্যক্তি লিস্ট।
- add(a,b) = (a%m + b%m)%m।
- solve(idx, mask): idx টুপি নম্বর, mask = কারা ইতিমধ্যে টুপি পেয়েছে।
- যদি mask == req (সবাই পেয়েছে), ১ রিটার্ন।
- যদি idx == 42, ০ রিটার্ন।
- dp[idx][mask] মেমোইজেশন।
- ret = add(ret, solve(idx+1, mask)) (এই টুপি কেউ নেয় না)।
- v[idx]-এর প্রতিটি ব্যক্তি i জন্য: যদি mask-এ i-তম বিট ০ হয়, ret = add(ret, solve(idx+1, mask | (1<
- dp[idx][mask] = ret রিটার্ন।
C++ কোড উদাহরণ
#include <bits/stdc++.h>
using namespace std;
typedef long long int lli;
int m = 1e9 + 7;
int dp[55][1 << 11];
class Solution {
public:
vector<vector<int>> v;
int req;
int add(lli a, lli b) { return ((a % m) + (b % m)) % m; }
int solve(int idx, int mask) {
if (mask == req) return 1;
if (idx == 42) return 0;
if (dp[idx][mask] != -1) return dp[idx][mask];
int ret = add(ret, solve(idx+1, mask));
for (int i : v[idx]) {
if (!((mask >> i) & 1))
ret = add(ret, solve(idx+1, mask | (1 << i)));
}
return dp[idx][mask] = ret;
}
int numberWays(vector<vector<int>>& x) {
memset(dp, -1, sizeof dp);
int n = x.size();
v.resize(50);
for (int i = 0; i < x.size(); i++)
for (int j : x[i]) v[j].push_back(i);
req = (1 << n) - 1;
int ret = solve(0, 0);
return ret;
}
};
int main() {
Solution ob;
vector<vector<int>> v = {{4,6,2},{4,6}};
cout << ob.numberWays(v);
return 0;
}
ইনপুট
{{4,6,2},{4,6}}
আউটপুট
4
