📝 문제 정보#
🧐 관찰 및 접근#
- 비트마스킹적으로 접근해보면, 여러 장난감 상자들의 or 연산결과가 $1111111..$이 되도록 하는 조합의 개수를 찾으면 되는 것 같다.
- $N$에 대해 생각하긴 까다로우므로, $M \leq 20$인 것을 이용해서 $M$에 대한 비트마스킹된 상자의 수로 생각해보자.
- 이후 과정을 포함배제로 진행하면 $O(2^N \times 2^N)$이겠지만, 우리는 SOS DP를 이용해서 $O(N2^N)$ 에 계산할 수 있음을 알 수 있다.
- 그런데 그냥 기본적인 SOS DP랑은 세팅이 조금 다른가? 고민해보자.
- 기본적인 SOS DP는 해당 비트마스크의 부분집합의 원소 개수의 합이다.
- 이번에 구해야하는건 해당 비트마스크를 만들어줄 수 있는 조합의 개수인데..
- 결국 어떤 상자 $110011$을 골랐다고 생각해보자.
- 그러면, $??11??$ 인걸 모두 고르면 된다.
- 이걸 부분집합으로 세긴 힘들지만, 뒤집어서 생각한다면 $??00??$을 찾는 것이고, 이건 $110011$의 부분집합의 개수와 같은 것 같다!
- 자기 자신을 세지 않도록 조심하자.
- 그런데 저 방법으로 세면, 두개의 or연산밖에 고려하지 못한다… 3개 이상인걸 고려하려면 DP 설계를 조금 더 잘해야 할 것 같다.
- 아하, 원래게 $??11??$인 개수를 안다면, 여기에서 한개 이상만 고르면 된다. 그 개수를 $\text{cnt}$라고 하면, $2^{\text{cnt}} - 1$이 성립하는거 같기도?
- 근데 다시 생각해보니, 뭐랄까 원래가 $??10??$$ 인거랑 $??01??$$ 인거랑이 합쳐져서 되는것들을 못세는거..같기도?
- 연산해서 $11$을 만들기 위해선, $(11 + 10 + 01 + 00)^2$ 같은 느낌으로 생각해보자.
- 저 연산 결과는
- $$ 11^2 + 10^2 + 01^2 + 00^2 + \\ 2(11\cdot10 + 11\cdot01 + 11\cdot00 + 10\cdot01 + 10\cdot00 + 01\cdot00) $$
- 이고, 잘 고민해보니 $11$의 부분집합의 제곱 - $11, 01$의 부분집합의 제곱 - $00$의 부분집합의 제곱을 하면 깔끔하게 $11^2 + 2(11\times10 + 11\times01 + 11\times00 + 10\times01)$이 된다.
- 아니 잠깐만, 저 느낌을 그대로 가져가면 그냥 부분집합의 합으로 SOS DP를 한다음에 포함배제를 때려버리면 어떻게든 된다. 연산결과가 $11...11$인놈들 - $(01...11), (10..111)...$ + $...$ 이렇게 하면 되는구나!
💻 풀이#
- 코드 (C++):
void solve(){
int N, M; cin >> N >> M;
vector<int> A(N);
rep(i, 0, N){
int K; cin >> K;
int ret = 0;
rep(j, 0, K){
int x; cin >> x;
ret |= (1 << (x-1));
}
A[i] = ret;
}
vector<int> SOS(1 << M, 0);
for(auto x: A) SOS[x] += 1;
rep(i, 0, M) rep(mask, 0, 1<<M) if(mask & (1 << i)) SOS[mask] += SOS[mask^(1<<i)];
mint ans = 0;
rep(mask, 0, 1<<M){
int cnt = 0;
rep(i, 0, M) if((mask & (1 << i)) == 0) cnt++;
if(cnt & 1) ans -= (mint(2).pow(SOS[mask]));
else ans += (mint(2).pow(SOS[mask]));
}
cout << ans << "\n";
}