백준 18465번 Horrible Cycles

문제 요약

크기가 $2n$인 이분그래프가 주어진다. 그래프는 왼쪽 오른쪽으로 나눠지고 각각 $n$개씩 정점이 존재한다.

$a_1, a_2, \cdots, a_n$이 주어진다. $a_i$는 왼쪽에서 $i$번째 정점에서 오른쪽으로 연결된 간선들에 대한 정보이다. 왼쪽에서 $i$번째 정점은 오른쪽에서 $1, 2, \cdots , a_i$번째 정점들에 연결되어 있다는 뜻이다.

이 때, 주어진 그래프에서 simple-vertex cycle의 수를 구하시오.

$ 1 \le n \le 5000$

풀이

왼쪽 정점들을 주어진 순서대로 볼 게 아니라 $a_i$를 정렬한 순서대로 봐도 상관 없다. 그리고 이게 풀이를 구성하는 데에 있어서 훨씬 쉬워진다.

먼저 simple-vertex cycle이 생겼다면 그건 어떻게 생겨먹었을까? 우린 이분그래프에서 사이클을 찾고 있는 것이기 때문에 그러한 사이클의 길이는 무조건 짝수일 것입니다. 그리고 왼쪽에 있는 점들을 시작점으로 잡는다면 정점들의 순서는 왼-오-왼-오-왼-오-왼 처럼 왼쪽 정점에서 시작해서 번갈아가면서 나오다가 왼쪽 정점에서 끝날 것입니다.

그리고 이러한 사이클에는 각 정점이 최대 한번만(simple-vertex) 등장할 수 있으므로 하나의 정점은 2개의 간선에 연결되어 있는 형태일 것입니다.

그러면 우리가 사이클을 찾는 방식으로 왼쪽 정점의 첫번째 정점부터 자신과 간선을 2개씩 선택해나가면서 사이클이 생기면 이를 답에 반영해주면 됩니다.

간선 2개를 어떻게 선택해야 사이클이 생길까요? 이를 알아보기 위해서 위와 같은 방식으로 그래프를 구성해나갔을 때 등장하는 컴포넌트의 형태를 살펴봐야 합니다. 먼저, 우리가 원하는 사이클의 형태로 존재할 수 있고, 사이클이 아니라면 오른쪽 정점을 시작으로 해서 오-왼-오-왼-오 처럼 오른쪽 정점으로 끝나는 path의 형태로 존재합니다. 이런 path에 양 끝 점에 간선을 연결하면 사이클이 생깁니다.

따라서, $i$번째 정점에서 간선을 2개 고를 때 생기는 사이클의 수는 $i-1$번째 정점까지를 사용했을 때 있는 unique한 path의 수와 동일합니다.

그러면 이 사실을 이용해서 dp를 생각해볼 수 있습니다. $dp(i, j)$를 $i$번째 정점까지 사용했을 때 저러한 $path$가 $j$개인 경우의 수라고 합시다.

그러면 $i$번째 정점을 추가할 때 생기는 사이클의 수는 $dp(i-1, 1)$이 됩니다. 이제 이런 path의 수를 잘 계산해야 합니다.

$i$번째 정점이 추가될 때 path의 수는 어떻게 변화될 수 있을까요? 두 개의 path를 골라서 하나의 path로 만들거나 사실 간선을 선택을 하지 않는다는 선택지도 있습니다.

따라서, $dp(i, j) = dp(i-1, j) + dp(i-1, j+1) \times (j+1)j$가 됩니다. 이제 상태전이는 정의가 됐습니다. 그런데 단순히 이것만을 사용해서 사이클의 수를 구하기엔 문제가 있습니다.

$a_{i-1} = a_i$일 때는 상관이 없는데 $a_{i-1} < a_i$일 때는 $i-1$번째 정점까지는 $a_{i-1} + 1, \ldots , a_i$까지는 사용하지 않기 때문입니다. 이것때문에 path가 아예 더해지는 경우도 생길 수 있고 줄어들 수도 있고, 그대로일 수도 있습니다. 이를 전부 고려해서 따져주는 것은 어렵습니다. (저는 여기서 한 8시간 막혀있었어요)

이를 해결하기 위한 좋은 방법은 $a_{i-1} + 1$부터 $a_i$까지의 오른쪽 정점들을 하나씩 추가하되, 크기가 1인 path로 간주하는 것입니다. 그리고 이를 $dp(i-1)$쪽에 추가해서 값들을 갱신해준 뒤에 $dp(i)$를 계산합니다.

그러면 계산이 쉬워집니다. 오른쪽 정점을 하나 추가할 때는 path수가 하나 늘어나는 것이기 때문에 $dp(i-1, j) = dp(i-1, j) + dp(i-1, j-1)$로 갱신해주면 됩니다.

여기까지 답을 구하고 출력하면 틀립니다. 우리가 오-왼-오 path가 아닌 오른쪽 정점 하나도 path 하나로 간주 했기 때문에 이것을 빼줘야 합니다. $a_i$의 합을 빼주면 됩니다.

그리고 사이클들이 전부 두 번씩 카운팅 됐으므로 2를 나눠줍니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
int N;

ll ipow(ll a, ll b) {
    ll ret = 1;
    while(b) {
        if(b & 1) ret = ret * a % mod;
        b >>= 1; a = a * a % mod;
    }
    return ret;
}

int main() {
    cin.tie(nullptr); ios::sync_with_stdio(false);
    cin >> N;
    vector<int> a(N+1);
    for(int i=1;i<=N;++i) cin >> a[i];
    sort(a.begin()+1, a.end());
    vector<ll> dp_cur(N+1, 0);
    dp_cur[0] = 1;
    vector<ll> dp_prev;
    int r_cnt = 0;
    ll ans = 0;
    for(int i=1;i<=N;++i) {
        while(r_cnt < a[i]) {
            dp_prev = dp_cur;
            for(int j=0;j<=r_cnt;++j) {
                dp_cur[j+1] += dp_prev[j];
                dp_cur[j+1] %= mod;
            }
            ++r_cnt;
        }
        dp_prev = dp_cur;
        ans += dp_cur[1];
        ans %= mod;             // cycle forms one component
        for(ll j=1;j<r_cnt;++j) {
            dp_cur[j] += dp_prev[j+1] * j * (j+1) % mod;
            dp_cur[j] %= mod;
        }
    }
    for(int i=1;i<=N;++i) ans = (ans - a[i] + mod) % mod;   // single vertex
    cout << ans * ipow(2, mod-2) % mod << '\n';     // remove double counting
    return 0;
}