SOS dp (Sum over Subsets)

Sum over Subsets 라는 이름답게, 부분집합의 합을 구하는 알고리즘이다.

구체적으로는, $F[mask] = \sum \limits_{i\subseteq mask} A[i]$를 구한다.

$0\leq mask < 2^N$일 때 $O(N2^N)$으로 동작한다.

for(int i = 0; i < (1 << N); i++) F[i] = A[i];
for(int j = 0; j < N; j++) for(int i = 0; i < (1 << N); i++)
	if(i & (1 << j)) F[i] += F[i ^ (1 << j)];

코드는 매우 간단하다. 이 알고리즘이 왜 성립하는지 알아보기 위해 위에서 설명한 시그마 식을 풀어서 보자.

$F[mask]$는, $mask$에서 0인 비트는 0이고 $mask$에서 1인 비트는 0 또는 1인 $mask'$에 대해 $A[mask']$의 합이다. 즉, $mask'$은 $mask$에 비해 일부 비트가 0일 수 있는 것이다.

위 코드의 첫 줄을 실행하면, $F[mask]$는 $mask = mask'$인 $mask'$에 대한 $A[mask']$의 합이다. 그리고 둘째 줄에서 $j$ 값 하나에 대한 연산을 시행할 때마다, $j$번째 비트가 0인 경우를 포함하게 된다.

따라서 이 알고리즘은 옳다는 것을 알 수 있다. 

자세한 설명은 https://codeforces.com/blog/entry/45223 참고.

 

나는 아래 문제들을 풀 때 SOS dp를 사용하였다.

Manthan, Codefest 19의 F. Bits and Pieces https://codeforces.com/contest/1208/problem/F

Codeforces Round #588 (Div. 1)의 E1. Marek and Matching (easy version) https://codeforces.com/contest/1229/problem/E1