SOS_DP

📝 상세 정리 # $2^N$개의 정수 배열 $A$가 주어진다. 이때 $\forall x$ 에 대해 $F(x)$를 $\sum\limits_{i \subseteq x}{A[i]}$ 라고 정의하자. 이는 $x\&i = i$ 인 $i$들에 대해 $A[i]$의 합을 의미한다. 위와 같은 문제를 어떻게 풀 수있을까? 브루트포스 # 느리지만, 다음과 같은 브루트포스로 계산할 수 있겠다. for(int mask = 0; mask < (1<<N); mask++){ for(int i = 0; i < (1<<N); i++){ if((mask&i) == i){ F[mask] += A[i]; } } } 위 식을 그대로 옮긴 것에 가깝다. 시간복잡도는 ${(2^N)}^2 = 4^N$이다. 조금 더 나은 풀이 # 두번째 반복문에 대해, 바깥쪽 반복문에서 켜지지 않은 비트에 대해서도 반복을 도는것은 너무 아깝다. 따라서 다음과 같이도 한번 시도해볼 수 있겠다. for(int mask = 0; mask < (1<<N); mask++){ F[mask] = A[0]; for(int i = 0; i < (1<<N); i = (i-1)&mask) F[mask] += A[i]; } 시간복잡도 증명이 어려워보인다. 이는 $\sum\limits_{k = 0}^N{\binom{N}{K}2^K} = 3^N$ 이라고 한다. Sum over Subsets DP # 위의 방식에서 병목은 어디에서 나타날까? 어떤 $x$의 비트가 $K$개가 꺼져있을 때, $A[x]$는 $2^K$개의 마스크에 의해 방문된다. 이 반복적인 재계산을 줄여야한다. S(mask, i) 정의 # 위 병목을 피하기 위해 새로운 상태를 하나 정의해보자. $S(mask, i)$는 $mask$의 부분집합들 중, $mask$와 하위(오른쪽) $i$개 비트(0~i-1번 인덱스)에서만 다른 것을 의미한다. 예를 들어, $S(110, 2) = \{100, 110\}$이다. 오른쪽 두개 비트에서 다를 수 있는데, 부분집합이어야 하므로 $111$같은건 안된다. 이 정의를 이용하면, 어떤 집합도 서로 겹치지 않는 $S(mask, i)$들의 합집합으로 나타낼 수 있게 된다. 점화식 유도 # 점화식은 다음과 같이 두가지로 정의할 수 있겠다. $mask$의 $i$번째 비트가 $0$인 경우 $mask$의 부분집합이 $i$번째 비트에서 $0$만을 가질 수 있으므로 $S(mask, i) = S(mask, i-1)$ $mask$의 $i$번째 비트가 $1$인 경우 $mask$의 부분집합이 $i$번째 비트에서 $0, 1$ 모두 가질 수 있으므로 $S(mask, i) = S(mask, i-1) \cup S(mask \oplus 2^i, i-1)$ 따라서 이를 코드로 나타내면 다음과 같다. for(int mask = 0; mask < (1<<N); mask++) DP[mask] = A[mask]; for(int i = 0; i<N; i++){ for(int mask = 0; mask < (1<<N); mask++){ if(mask & (1<<i)) DP[mask] += DP[mask ^ (1<<i)]; } } 계산 결과 DP에 들어있는 값은 해당 비트마스킹의 부분집합의 합이다. 시간복잡도는 그대로 보이듯이 $O(N2^N)$이다. N차원 누적합 # https://blog.queuedlab.com/posts/sos-dp 를 참고하면, 이를 $N$차원 누적합으로도 해석할 수 있다. 하이퍼 수열과 하이퍼 쿼리 문제에서 $N$차원 누적합 아이디어는 써본적이 있었는데, 이것이 SOS DP와 같다는 것이 신기하다. 앞으로는 포함배제에서 뭔가 줄이고싶으면 한번씩은 의심해보는걸로? imos-hanbyul Trick # 이와 비슷한 내용을 https://qwerasdfzxcl.tistory.com/35 여기서 본적이 있다. 지금 당장은 이해하기 귀찮으므로 이해한 내용은 나중에 추가하겠다. ❔질문 사항 # 🔗 참고 자료 # https://codeforces.com/blog/entry/45223 https://blog.queuedlab.com/posts/sos-dp https://qwerasdfzxcl.tistory.com/35

📝 문제 정보 # 링크: https://www.acmicpc.net/problem/2803 🧐 관찰 및 접근 # 비트마스킹적으로 접근해보면, 여러 장난감 상자들의 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"; } 🔒 구현 코드 잠금