n명의 사람과 1에서 40까지 레이블이 지정된 40가지 다른 유형의 모자가 있다고 가정합니다. 이제 hats라고 하는 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() 함수를 정의하면, b,
-
return ((a mod m) + (b mod m)) mod m
-
solve() 함수를 정의하면 idx, mask,
가 필요합니다. -
마스크가 req와 같으면 -
-
1 반환
-
-
idx가 42와 같으면 -
-
0 반환
-
-
dp[idx, mask]가 -1과 같지 않으면 -
-
반환 dp[idx, 마스크]
-
-
ret :=add(ret, solve(idx + 1, 마스크))
-
v[idx]sk의 모든 i에 대해))
-
(오른쪽으로 이동 마스크 i 비트)가 짝수이면
-
ret =add(ret, solve(idx + 1, 마스크 OR 2^i))
-
-
-
dp[idx, 마스크] :=ret
-
리턴 렛
-
주요 방법에서 다음을 수행하십시오 -
-
-1로 dp 초기화
-
n :=x의 크기
-
50개 요소를 포함할 수 있도록 v 업데이트
-
initialize i :=0의 경우, i
-
x[i]의 모든 j에 대해
-
v[j]
끝에 i 삽입
-
-
-
필수 :=(2^n) - 1
-
ret :=해결(0, 0)
-
리턴 렛
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
예시
#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