C++でのビットマスキングと動的計画法

1から50までの数字の50のキャップがあります。N人はコレクションにこれらのキャップのいくつかを持っています。ある日、彼ら全員がパーティーに帽子をかぶる。しかし、すべてがユニークに見える必要があるので、彼らはそれぞれ異なる番号のキャップを着用することにしました。コレクションには、n人の人数とキャップ番号が与えられます。私たちの仕事は、誰もがユニークに見えるように、キャップを着用できる方法の総数を見つけることです。

この問題では、最初の行に値n、つまり人数が含まれています。次のn行にはコレクションが含まれています。

入力 −

3
4 45 10
25
45 10

出力 −

4

説明 −

考えられるすべての方法は、（4、25、45）、（4、25、10）、（45、25、10）、（10、25、45）です。

ウェイの数が多くなる可能性があるため、出力は1000000007の形式にする必要があります。

この問題を解決するための簡単な解決策は、キャップを使用している人々のすべての可能な組み合わせを見つけることです。最初のセットから開始して、残りのセットを繰り返します。ただし、このソリューションは最適化されていません。

より良い解決策は、10人用にサイズ210のマスクを作成することにより、ビットマスキングとDPを使用することです。そして、サイズ51のキャップのベクトル。次に、さまざまな方法で繰り返します。

例

ソリューションの実装を示すプログラム −

#include<bits/stdc++.h>
using namespace std;
vector<int> caps[101];
int dp[1025][101];
int allmask;
long long int uniqueCaps(int mask, int i) {
   if (mask == allmask) return 1;
   if (i > 100) return 0;
   if (dp[mask][i] != -1) return dp[mask][i];
   long long int ways = uniqueCaps(mask, i+1);
   int size = caps[i].size();
   for (int j = 0; j < size; j++) {
      if (mask & (1 << caps[i][j])) continue;
         else ways += uniqueCaps(mask | (1 << caps[i][j]), i+1);
         ways %= (1000000007);
      }
      return dp[mask][i] = ways;
   }
int main() {
   int n = 3;
   // Collection of person 1
   caps[4].push_back(0);
   caps[45].push_back(0);
   caps[10].push_back(0);
   // Collection of person 2
   caps[25].push_back(1);
   // Collection of person 3
   caps[45].push_back(2);
   caps[10].push_back(2);
   allmask = (1 << n) - 1;
   memset(dp, -1, sizeof dp);
   cout<<"The number of ways the person can wear unique cap in party is:\t"<<uniqueCaps(0, 1);
   return 0;
}

出力

The number of ways the person can wear unique cap in party is: 4