समस्या विवरण
मान लीजिए n लोग हैं और 40 विभिन्न प्रकार की टोपियाँ हैं जो 1 से 40 तक लेबल की गई हैं। अब एक 2D सूची दी गई है जिसे hats कहा जाता है, जहां hats[i] i-वें व्यक्ति द्वारा पसंद की गई सभी टोपियों की सूची है। हमें उन तरीकों की संख्या ज्ञात करनी है जिनसे n लोग एक-दूसरे से अलग टोपी पहन सकते हैं। उत्तर बहुत बड़ा आ सकता है, इसलिए उत्तर को 10^9 + 7 से मॉड्यूलो करके लौटाएं।
उदाहरण
यदि इनपुट है: [[4,6,2],[4,6]], तो आउटपुट होगा 4, क्योंकि चुनने के 4 अलग-अलग तरीके हैं: [4,6], [6,4], [2,4], [2,6]।
हल करने का दृष्टिकोण
इस समस्या को हल करने के लिए निम्नलिखित चरणों का पालन करें (DP + बिटमास्किंग):
- m = 10^9 + 7
- आकार 55 x 2^11 का 2D सरणी dp परिभाषित करें
- एक 2D सरणी v परिभाषित करें
- add() नामक एक फ़ंक्शन परिभाषित करें, जो a, b लेता है:
- ((a % m) + (b % m)) % m लौटाएं
- solve() नामक एक फ़ंक्शन परिभाषित करें, जो idx, mask लेता है:
- यदि mask, req के समान है, तो 1 लौटाएं
- यदि idx, 42 के समान है, तो 0 लौटाएं
- यदि dp[idx][mask] != -1, तो dp[idx][mask] लौटाएं
- ret := add(ret, solve(idx + 1, mask))
- v[idx] में सभी i के लिए:
- यदि (mask को i बिट्स राइट शिफ्ट) सम है:
- ret = add(ret, solve(idx + 1, mask | (1 << i)))
- यदि (mask को i बिट्स राइट शिफ्ट) सम है:
- dp[idx][mask] := ret
- ret लौटाएं
- मुख्य विधि से:
- dp को -1 से आरंभ करें
- n := x का आकार
- v को अपडेट करें ताकि इसमें 50 तत्व हो सकें
- i := 0 से आरंभ करें, जब i < x का आकार, i को 1 से बढ़ाते हुए:
- x[i] में सभी j के लिए:
- i को v[j] के अंत में डालें
- x[i] में सभी j के लिए:
- req := (2^n) - 1
- ret := solve(0, 0)
- 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(0, 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