C++で互いに異なる帽子をかぶる方法の数

1から40までのラベルが付けられたn人と40種類の帽子があるとします。ここで、帽子と呼ばれる2Dリストが与えられます。ここで、hats[i]はすべての帽子のリストです。 i番目の人が好む。 n人がお互いに異なる帽子をかぶる方法の数を見つける必要があります。答えは非常に大きくなる可能性があるため、10 ^ 9+7を法として答えを返します。

したがって、入力が[[4,6,2]、[4,6]]の場合、出力は4になります。これは、[4,6]、[6、 4]、[2,4]、[2,6]。

これを解決するには、次の手順に従います-

• m =10 ^ 9 + 7

• サイズ55x2^11の2D配列dpを定義します

• 1つの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、mask]

    を返します

• ret：=add（ret、solve（idx + 1、mask））

• v [idx] sk））

  のすべてのi

  • （マスクをiビット右にシフト）が偶数の場合、

    • ret =add（ret、solve（idx + 1、mask OR 2 ^ i））

• dp [idx、mask]：=ret

• retを返す

• メインの方法から、次のようにします-

• dpを-1で初期化します

• n：=xのサイズ

• 50個の要素を含めることができるようにvを更新します

• 初期化i：=0の場合、i

  • x [i]

    のすべてのj

    • v [j]

      の最後にiを挿入します

• req：=（2 ^ n）-1

• ret：=resolve（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