在C ++中互相戴不同帽子的方式数量

假设有n个人和40种不同类型的帽子，它们的标记范围是1到40。现在给出一个2D列表，称为帽子，其中hats [i]是第i个人所喜欢的所有帽子的列表。我们必须找到使n个人戴着不同帽子的方式的数量。答案可能非常大，因此请以10 ^ 9 + 7为模返回答案。

因此，如果输入类似于[[4,6,2]，[4,6]]，则输出将为4，因为有4种不同的选择方式，分别是[4,6]，[6， 4]，[2,4]，[2,6]。

为了解决这个问题，我们将遵循以下步骤-

list-paddingleft-2">

• m = 10 ^ 9 + 7

• 定义大小为55 x 2 ^ 11的2D数组dp

• 定义一个2D数组v

• 定义一个函数add()，这将需要a，b，

• return（（a mod m）+（b mod m））mod m

• 定义一个函数solve()，它将使用idx，mask，

• 如果mask与req相同，则-

• 返回1

• 如果idx与42相同，则-

• 返回0

• 如果dp [idx，mask]不等于-1，则-

• 返回dp [idx，掩码]

• ret：=添加（ret，resolve（idx + 1，mask））

• 对于v [idx] sk中的所有我））

• ret =添加（ret，resolve（idx + 1，mask OR 2 ^ i））

• 如果（移位掩码i位向右）是偶数，则

• dp [idx，mask]：= ret

• 返回ret

• 从主要方法中执行以下操作-

• 用-1初始化dp

• n：= x的大小

• 更新v，使其可以包含50个元素

• 对于初始化i：= 0，当i <x的大小时，更新（将i增加1），执行-

• 在v [j]的末尾插入i

• 对于x [i]中的所有j

• 要求：=（2 ^ n）-1

• ret：= solve(0,0)

• 返回ret

让我们看下面的实现以更好地理解-

示例

#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