BOJ #13130 - FunctionCup

Sum over subsets DP 연습문제를 찾다가 만난 흥미로운 문제다 (스포일러: 다만 이 문제자체는 SOS DP 는 사용하지 않는다). FunctionCup 대회의 문제이지만 예비소집 문제라서 해설이 없어 적어본다.

BOJ #13130 - FunctionCup

함수 $f$ 는 집합 $S$ 에서 $S \to S$ 인 전단사 함수이다. 이는 집합의 순열과 같다고 생각해볼 수 있다.

함수 $f$ 를 나타내는 순열그래프를 생각해보자. 순열 그래프는 여러개의 사이클로만 이루어져 있음을 알 수 있다 (self-loop 도 cycle 의 일종이라고 생각한다면). 만약 순열 그래프상에서 집합 $S$ 의 어떤 원소 $x$ 가 속해있는 사이클의 길이가 $k$ 라면 (자명하게도) $f^k(x)=x$ 임이 만족될 것이다 (i). 그런데 문제의 조건에 의하면 구간 $[1,N]$ 안의 모든 $i$ 에 대해서 $f^{A_i}(i)=i$ 를 만족해야한다 (ii). 정의역 $S$ 상의 순열 그래프에서 어떤 사이클이 있을때 이 사이클이 문제의 주어진 조건에 부합하는지 위반하는지 체크하는 방법은 사이클을 구성하는 원소들의 집합을 $S'$ 이라고 했을 때, $S'$ 집합의 크기, 즉 사이클의 길이 $|S'|$ 가 $\gcd(A_{S'_1},A_{S'_2},...,A_{S'_{|S'|}})$ 의 약수여야만 위 두가지 제약 조건 (i, ii) 을 만족하는 유효한 사이클이다. 집합 $S$ 의 모든 부분집합 $S'$ 에 대하여 $dp(S')$ 을 $S'$ 의 원소만을 모두 사용해서 순열 그래프를 구성했을 때의 경우의 수를 저장해서 전체 해를 구해보자. 문제에서 주어진 $N$ 의 범위가 충분히 작기 때문에, 비트마스킹을 통해 집합을 표현하면 메모리 초과에 대해 걱정할 일이 없다. 다음은 점화식이다:

집합 상태 $S'$ 에서 $S$ 로 전이될때 차집합 $S-S'$ 의 원소들로 이루어진 사이클 하나가 추가되면서 이전 상태의 DP 값에 $|S-S'|-1$ 만큼 곱해져서 더해지고 있다. 차집합 $S-S'$ 의 원소들로 사이클을 하나 만드는 경우의 수는 이 원소들로 원순열 하나를 만드는 문제와 같아서 차집합만큼의 크기가 아니라 차집합의 크기에서 -1된 값의 팩토리얼을 곱하고 있음에 주목하자.

현재 상태에서 사이클을 하나씩 올려가는 방식의 이 풀이를 사용할 때 유의해야할 점은 같은 함수 $f$ 가 만들어져서 중복되서 답이 계산되는 상태를 방지하기 위해 사이클이 추가되는 순서를 고정해야 한다는 점이다. (아니면 지독한 포함-배제의 늪에 빠져버릴 수 있다...) 예를 들어 집합에 나는 현재 상태 $S'$ 에 차집합 $S-S'$ 만큼 더해서 $S$ 에 대한 dp 값을 계산하고 있는데, 더해지는 차집합의 bit 표현이 큰 경우만 고려하는 방식으로 순서를 고정했다.

(혹시 중복이 발생하는 경우가 이해되지 않는다면 간단한 예시를 생각해보자: $dp(111) = dp(101) + 010$ 는 이미 1, 3번째 요소가 현재 상태에 고려된 상태에서 2번째 요소가 self-loop 를 이루는 경우의 수를, $dp(111) = dp(110) + 001$ 는 이미 2, 3번째 요소가 고려된 상태에서 1번째 요소가 self-loop 를 이루는 경우의 수를 고려해서 각각 $dp(111)$ 상태에 기여되고 있는데, 집합이 더해지는 순서를 고려하지 않아 1, 2, 3번째 요소 모두 self-loop 를 이루는 경우를 중복집계하고 있다.)

크기가 $N$ 인 집합 $S$ 의 모든 부분집합 $S'$ 에 대하여 모든 부분집합에 대하여 iteration 이 수행되기 때문에 $\sum_{i=0}^N {N\choose{i}}\cdot2^i=3^N$ 이므로 전체 시간복잡도는 $O(3^N)$ 이다.

소스 코드:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int rgcd[1 << 16];
ll dp[1 << 16], fac[17];
bool vg[1 << 16];

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (auto& ai : a) cin >> ai;
    for (int i = 1; i < (1 << n); i++) {
        for (int j = 0; j < n; j++)
            if (i & (1 << j)) rgcd[i] = gcd(rgcd[i], a[j]);
        if (rgcd[i] % __builtin_popcount(i) == 0) vg[i] = true;
    }
    fac[0] = 1;
    for (int i = 1; i <= 16; i++) fac[i] = i * fac[i - 1];

    dp[0] = 1;
    for (int i = 1; i < (1 << n); i++) {
        int cnt = __builtin_popcount(i);
        if (vg[i]) dp[i] = fac[cnt - 1];

        for (int j = i & (i - 1); j > 0; j = (j - 1) & i) {
            int res = i - j;
            if (res > j && vg[res]) {
                dp[i] += dp[j] * fac[__builtin_popcount(res) - 1];
            }
        }
    }

    cout << dp[(1 << n) - 1] << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    solve();
    return 0;
}

References

• Sum over Subsets (SOS) DP - SOS DP 에 대한 포스트이지만, SOS DP 에서 사용되는 submask 탐색에 대한 설명이 좋으니 꼭 읽어보길 추천드린다.