82. Sum Over Subsets

집합이 존재할 때 각각의 부분집합에 대해 그 집합의 부분집합의 합(Sum Over Subsets, SOS)을 빠르게 계산하는 방법에 대해서 다룬다. 이 방법은 DP 테이블을 채우면서 부분집합의 합을 계산하기 때문에 SOS DP라고 불린다. 원소의 개수가 $n$인 집합의 부분집합의 개수가 $2^n$이고, SOS DP의 기본 시간복잡도가 $\Theta(2^n \cdot n)$이기 때문에 일반적으로 $n$은 $20$ 이하이다.

 

SOS DP는 집합을 비트마스크로 표현하며, 따라서 비트필드를 이용하게 된다. 집합을 0-based로 나타내면 $0 \le p < 2^n$을 만족하는 정수 $p$는 $p$의 켜진 비트에 해당하는 원소들을 포함하는 집합을 나타내는 것으로 생각할 수 있다. 예를 들어 $0$번째, $3$번째 원소를 포함하는 집합은 $2^0 + 2^3 = 9$라는 정수로 표현하게 되고 $1$번째, $3$번째, $6$번째 원소를 포함하는 집합은 $2^1 + 2^3 + 2^6 = 74$라는 정수로 표현하게 된다. 이 방법으로 집합을 표현할 경우 두 집합의 포함 관계는 다음과 같이 확인할 수 있다.

 

• 두 집합 $A, B$를 나타내는 정수가 각각 $x, y$일 때 $(x \And y) = y$인 경우 $B \subset A$이고 $(y \And x) = x$인 경우 $A \subset B$이다.

이 사실을 바탕으로 다음과 같이 DP 식을 정의한다. $S_p$는 정수 $p$로 표현되는 집합을 의미한다.

$$a[p][0] = \left\vert S_p \right\vert$$

$$a[p][k] = a[p][k-1] + \begin{cases} 0 & (p \And 2^{k-1} = 0) \\ a[p-2^{k-1}][k-1] & (p \And 2^{k-1} = 2^{k-1}) \end{cases} (0 < k < n)$$

$a[p][k]$는 집합 $S_p$의 각각의 부분집합을 표현하는 수들 중 $k$번째 이상의 비트가 $p$의 $k$번째 이상의 비트와 전부 일치하는 집합의 원소들의 합을 의미한다.

이 방법으로 비트필드를 채우면 $a[p][n]$에 $p$의 부분집합의 합이 저장된다. 다음과 같이 구현할 수 있다.

void sos(int n)
{
    for(int i = 0; i < 1 << n; i++)
    {
        for(int j = 1; j <= n; j++)
        {
            a[i][j] = a[i][j - 1];
            if(i & 1 << j - 1)a[i][j] += a[i - (1 << j - 1)][j - 1];
        }
    }
}

 

[참고 링크]

 

블로그

 

[연습문제]

 

BOJ 18719. Binomial (Diamond V)

뤼카 정리에 의하면 $n\choose k$가 홀수인 경우는 $(n \And k) = k$인 경우와 같다. 따라서 입력되는 각각의 값의 개수를 $a[p][0]$에 저장한 다음 SOS DP를 이용해서 문제를 해결할 수 있다. 구하는 답은 $\sum_{i=0}^{2^{20}-1} a[i][0] \cdot a[i][20]$이 된다.

 

→ solved.ac tag: dp_sum_over_subsets