假设有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]。
为了解决这个问题,我们将遵循以下步骤-
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