Sum Over Subsets

백준 18719번 Binomal 문제풀이

[18719 Binomal] https://www.acmicpc.net/problem/18719 .
SOS DP를 이용하여 부분집합의 합을 빠르게 구해보자.

다이아 문제를 탐색하던 중 5개월 전에 풀다가 ‘당연하게도’ 실패한 Binomal문제가 눈에 들어왔고 열심히 다시 풀어봤는데 안됐다 ㅠㅠ
블로그를 탐색해보니 SOS dp를 이용하는 것이라고 하여 이를 찾아봤다.
그랬더니 binomal문제가 아름답게 보였다 ㄷㄷ 이렇게 깔끔하게 홀수임을 판별하다니 ㅠㅠ
이에 대해서 알아보자

문제상황 파악하기.

배열이 주어지고 그 배열에서 한쌍 (i, j) 를 뽑아서 이항계수를 만들었을 때 그것이 홀수인 쌍의 개수를 구하는 문제이다.
이를 5개월 전(골드일때인가?) 시도 했을 때는 이항계수를 2로 나눈 값을 전처리해서 풀려고 했었고 지금 보니 O(n^2)으로 풀어서 당영히 시간초과다.
그럼 이 문제는 어떻게 풀어야 할까?

Sum Over Subsets가 뭐길래?

비트마스킹을 이용해서 부분 집합의 합을 바르게 구하는 방법이다.
예를 들어서 1011101의 부분집합의 개수를 구하고 싶으면 각자리 수를 포함하는지 안하는지를 보면서 가야한다.
일단 dp[i][k]는 i의 상태(state)와 k까지만 일치하는 것들의 부분집합의 개수이다.
말을 좀 이상하게 한 것 같은데 dp[1101][0]의 개수는 1101의 상태를 가진 것의 개수인 것이다.
dp[1101][1]은 110까지는 같은데 그 이후는 다를 수도 있는 것의 개수이다. 즉 1101또는 1100이 될 것이다.
그러니까 k-1번째 자리에서 0이면 그자리는 선택하면 안되니까

• dp[i][k] = dp[i][k-1]이다.

근데 k-1번째 자리가 1이면 그 자리는 선택해도되고 안해도 되니까

• dp[i][k] = dp[i][k-1] + dp[i-(1«k-1)][k-1]이 된다.

for(int i=1;i<(1<<20);i++){
    for(int j=1;j<21;j++){
        dp[i][j] = dp[i][j-1];
        if(i&(1<<(j-1))) dp[i][j] += dp[i-(1<<(j-1))][j-1];
    }
}

아이디어 얻기.

모든 자연수는 2로 나누면 0또는 1이다.
그리고 뤼카정리를 이용하면 이항계수를 이진수 이항계수의 곱으로 나타낼 수 있다.
이 때 하나라도 0이 있으면 곱셈이기때문에 총 0이되고 이는 짝수라는 것이다.
그러니까 부분집합이여야지만 홀수가 나온다.(15C6 같은걸로 해보자)
dp[i][0] : 배열에 i가 몇개 있음? dp[i][20] : 배열에 i보다 작거나 같은게 몇개 있음? 따라서 모든 홀수는 dp[i][0]*dp[i][20]을 곱한값을 모든 i에 대해 더해주면 된다.

주의할 점

Sum Over Subsets DP table을 잘 구했다면 아무 문제 없다.

실제 코드

나머지 주의 할 점은 코드에 주석으로 처리했다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <cstring>
#include <stack>
#include <queue>
#include <cmath>
#include <set>
#include <map>
#include <cassert>
#define fast_io cin.tie(NULL); ios_base::sync_with_stdio(false);
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int n;
vector<int> a;
ll dp[1<<20][21];

int main(){
    fast_io
    int tt; cin>>tt;
    while (tt--) {
        cin >> n;
        a = vector<int> (n);
        for(int i=0;i<n;i++){
            cin >> a[i];
            dp[a[i]][0]++;
        }
        for(int i=1;i<(1<<20);i++){
            for(int j=1;j<21;j++){
                dp[i][j] = dp[i][j-1];
                if(i&(1<<(j-1))) dp[i][j] += dp[i-(1<<(j-1))][j-1];
            }
        }
        ll res = 0;
        for(int i=0;i<(1<<20);i++){
            res += dp[i][0]*dp[i][20];
        }
        cout << res << '\n';
        
        memset(dp, 0, sizeof(dp));
    }
}