C++ এ একে অপরকে বিভিন্ন টুপি পরার উপায়ের সংখ্যা

ধরুন সেখানে n মানুষ এবং 40টি বিভিন্ন ধরণের টুপি আছে যেগুলিকে 1 থেকে 40 পর্যন্ত লেবেল করা হয়েছে৷ এখন একটি 2D তালিকা দেওয়া হয়েছে যাকে বলা হয় টুপি, যেখানে টুপিগুলি হল সমস্ত টুপির একটি তালিকা৷ i-th ব্যক্তির দ্বারা পছন্দ করা হয়. n মানুষ একে অপরের কাছে বিভিন্ন টুপি পরার উপায় আমাদের খুঁজে বের করতে হবে। উত্তরটি খুব বড় হতে পারে, তাই উত্তর মডিউল 10^9 + 7 ফেরত দিন।

সুতরাং, যদি ইনপুটটি [[4,6,2],[4,6]] এর মত হয়, তাহলে আউটপুট হবে 4, যেহেতু বেছে নেওয়ার 4টি ভিন্ন উপায় রয়েছে, এগুলো হল [4,6], [6, 4], [2,4], [2,6]।

এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -

• m =10^9 + 7

• 55 x 2^11 আকারের 2D অ্যারে ডিপি

  সংজ্ঞায়িত করুন

• একটি 2D অ্যারে v

  সংজ্ঞায়িত করুন

• একটি ফাংশন add() সংজ্ঞায়িত করুন, এটি a, b,

  লাগবে

• ফিরুন ((a mod m) + (b mod m)) mod m

• একটি ফাংশন সল্ভ(), এটি আইডিএক্স, মাস্ক,

  লাগবে

• মাস্ক যদি req এর মত হয়, তাহলে −

  • রিটার্ন 1

• যদি idx 42 এর মত হয়, তাহলে −

  • রিটার্ন 0

• যদি dp[idx, mask] -1 এর সমান না হয়, তাহলে −

  • dp[idx, mask]

    ফেরত দিন

• ret :=add(ret, solve(idx + 1, mask))

• সকলের জন্য আমি v[idx]sk))

  • যদি (মাস্ক আই বিট ডানদিকে স্থানান্তর) জোড় হয়, তাহলে

    • ret =add(ret, solve(idx + 1, mask OR 2^i))

• dp[idx, mask] :=ret

• রিটার্ন রিটার্ন

• প্রধান পদ্ধতি থেকে নিম্নলিখিতগুলি করুন -

• -1

  দিয়ে dp আরম্ভ করুন

• n :=x এর আকার

• v আপডেট করুন যাতে এতে 50টি উপাদান থাকতে পারে

• আরম্ভ করার জন্য i :=0, যখন i

  • x[i]

    -এ সকল j-এর জন্য

    • v[j]

      এর শেষে i ঢোকান

• req :=(2^n) - 1

• ret :=সমাধান (0, 0)

• রিটার্ন রিটার্ন

আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -

উদাহরণ

#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;
   }
};
main(){
   Solution ob;
   vector<vector<int>> v = {{4,6,2},{4,6}};
   cout << (ob.numberWays(v));
}

ইনপুট

{{4,6,2},{4,6}}

আউটপুট

4