Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में प्रत्येक को अलग-अलग टोपी पहनाने के तरीकों की संख्या


समस्या विवरण

मान लीजिए 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)))
    • dp[idx][mask] := ret
    • ret लौटाएं
  • मुख्य विधि से:
    • dp को -1 से आरंभ करें
    • n := x का आकार
    • v को अपडेट करें ताकि इसमें 50 तत्व हो सकें
    • i := 0 से आरंभ करें, जब i < x का आकार, i को 1 से बढ़ाते हुए:
      • x[i] में सभी j के लिए:
        • i को v[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
  1. C++ में N×3 ग्रिड को रंगने के तरीकों की संख्या C++ में N×3 ग्रिड को रंगने के तरीकों की संख्या

    समस्या विवरण मान लीजिए हमारे पास n x 3 आकार का एक ग्रिड है और हम ग्रिड के प्रत्येक सेल को तीन रंगों में से ठीक एक से रंगना चाहते हैं। रंग हैं लाल, पीला या हरा। अब एक प्रतिबंध है कि कोई भी दो आसन्न सेल का रंग समान नहीं होना चाहिए। हमारे पास n ग्रिड की पंक्तियों की संख्या है। हमें उन तरीकों की संख्या

  1. - C++ में वेरिएबल नंबर ऑफ आर्गुमेंट्स

    कभी-कभी, आप एक ऐसी स्थिति का सामना कर सकते हैं, जब आप एक ऐसा फंक्शन चाहते हैं, जो वेरिएबल नंबर ऑफ आर्गुमेंट्स ले सके, यानी, पैरामीटर्स, पूर्वनिर्धारित संख्या के पैरामीटर्स के बजाय। C/C++ प्रोग्रामिंग लैंग्वेज इस स्थिति के लिए एक समाधान प्रदान करती है और आपको एक ऐसा फंक्शन डिफाइन करने की अनुमति देती

  1. - C++ में CHAR_BIT

    CHAR_BIT क्या है? CHAR_BIT एक बाइट में बिट्स की संख्या दर्शाता है। <climits> या <limits.h> हेडर में परिभाषित। आमतौर पर 8 बिट्स प्रति बाइट होता है। C++ प्रोग्राम उदाहरण #include <bits/stdc++.h> using namespace std; int main() { int x = 28; int total_bits = CHAR_BIT * size