Số cách đội mũ khác nhau cho nhau trong C ++

Giả sử có n người và 40 loại mũ khác nhau được gắn nhãn từ 1 đến 40. Bây giờ, một danh sách 2D được đưa ra gọi là mũ, trong đó mũ [i] là danh sách tất cả các mũ được người thứ i ưa thích. Ta phải tìm số cách sao cho n người đội mũ khác nhau. Câu trả lời có thể rất lớn, vì vậy hãy trả về mô-đun câu trả lời 10 ^ 9 + 7.

Vì vậy, nếu đầu vào là [[4,6,2], [4,6]], thì đầu ra sẽ là 4, vì có 4 cách khác nhau để chọn, đây là [4,6], [6, 4], [2,4], [2,6].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

m =10 ^ 9 + 7
Xác định dp mảng 2D có kích thước 55 x 2 ^ 11
Xác định một mảng 2D v
Xác định một hàm add (), điều này sẽ lấy a, b,
return ((a mod m) + (b mod m)) mod m
Xác định một hàm giải quyết (), điều này sẽ lấy idx, mặt nạ,
nếu mặt nạ giống như yêu cầu, thì -
- trả lại 1
nếu idx bằng 42 thì -
- trả về 0
nếu dp [idx, mask] không bằng -1 thì -
- trả về dp [idx, mask]
ret:=add (ret, giải quyết (idx + 1, mask))
cho tất cả tôi trong v [idx] sk))
- nếu (shift mask i bit sang phải) là chẵn thì
  - ret =add (ret, giải quyết (idx + 1, mask HOẶC 2 ^ i))
dp [idx, mask]:=ret
trả lại ret
Từ phương thức chính, thực hiện như sau -
khởi tạo dp với -1
n:=kích thước của x
cập nhật v để nó có thể chứa 50 phần tử
để khởi tạo i:=0, khi i
- cho tất cả j trong x [i]
  - chèn tôi vào cuối v [j]
yêu cầu:=(2 ^ n) - 1
ret:=giải quyết (0, 0)
trả lại ret

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

Ví dụ

#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));
}

Đầu vào

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

Số cách đội mũ khác nhau cho nhau trong C ++

Ví dụ

Đầu vào

Đầu ra