UCPC 2020 C / 함수 복원 - 19544

#include <iostream>
#include <vector>
using namespace std;
 
const int MOD = 1000000007;
 
int N;
int arr[500][500];
vector<int> cyidx;
vector<vector<int>> cycleMem;
vector<vector<int>> aroundMem;
vector<long long> bucket;
 
long long cal2(long long u, long long v) {
    long long ret = 1;
    while(v) {
        ret *= u;
        ret %= MOD;
        --v;
    }
    return ret;
}
 
long long cal(long long u, long long v) {
    
    long long ret = 1;
    while(v) {
        ret *= u;
        ret %= MOD;
        --u;
        --v;
    }
    return ret;
}
 
int main() {
    ios_base::sync_with_stdio(0), cin.tie(0);
    cin >> N;
    cyidx = vector<int>(N, -1);
    for(int i = 0; i<N; ++i)
        for(int j = 0; j<N; ++j)
            cin >> arr[i][j];
    
    for(int i = 0; i<N; ++i)
        for(int j = i+1; j<N; ++j) {
            if(arr[i][j] && arr[j][i]) {
                if(cyidx[i] == -1 && cyidx[j] == -1) {
                    cycleMem.push_back(vector<int>());
                    cyidx[i] = cyidx[j] = cycleMem.size()-1;
                    cycleMem[cyidx[i]].push_back(i);
                    cycleMem[cyidx[i]].push_back(j);
                }
                else if(cyidx[j] == -1) {
                    cyidx[j] = cyidx[i];
                    cycleMem[cyidx[j]].push_back(j);
                }
            }
        }
    aroundMem = vector<vector<int>>(cycleMem.size());
    for(int i = 0; i<cycleMem.size(); ++i) {
        int base = cycleMem[i][0];
 
        for(int j = 0; j<N; ++j) {
            if(cyidx[j] == -1 && arr[j][base]) {
                int cnt = 0;
                for(int k = 0; k<N; ++k)
                    if(arr[j][k]) ++cnt;
                --cnt;
                if(cnt == cycleMem[i].size())
                    aroundMem[i].push_back(j);
            }
        }
    }
 
    bucket = vector<long long>(cycleMem.size(), 1);
    for(int i = 0; i<cycleMem.size(); ++i) {
        long long res = cal(cycleMem[i].size() - 1, cycleMem[i].size() - 1);
        long long res2 = cal2(cycleMem[i].size(), aroundMem[i].size());
        bucket[i] = res*res2;
        bucket[i] %= MOD;
    }
    long long ans = 1;
    for(int i = 0; i<cycleMem.size(); ++i) {
        ans *= bucket[i];
        ans %= MOD;
    }
    cout << ans;
}

 

 

 

 

 

 

https://www.acmicpc.net/problem/19544

19544번: 함수 복원

 

 

 

 

 

 

함수 복원

함수들을 그래프로 표현한다면, 모든 노드에서 나가는 간선은 오직 1개인 노드들로 이루어진 그래프가 그려집니다.

따라서 각각 연결된 그래프를 이루는 집합끼리 나누고,

해당 집합 안에선 (싸이클을 이루는 노드들로 원에 줄 세우는 경우의 수) * (싸이클을 이루는 노드가 아닌 노드중 싸이클과 인접한 노드의 개수를 싸이클의 노드들에 각각 붙이는 경우의 수)

를 구하고,

집합 각각에서 구한 위의 값들을 모두 곱해주면 답이 됩니다.