색칠 공부

graph, number of cases

출처: BOJ 색칠 공부

SOL)
size가 4부터
싸이클이의 점화식이 아래와 코드와 같이 나온다.
dfs를 통해 싸이클의 사이즈를 알아내고
ans에 곱해준 후 total_cycle에 사이즈를 더해준다.

마지막으로 처리가 되지 않은 직선 점들을 처리해준다.


[-] Collapse

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<climits>
#include<cmath>
using namespace std;
typedef long long ll;

#define y1 mine
#define mp make_pair

double pi = acos(-1);

const ll mod = 1000000007;
const int N = 1000010;
int visit[N];
ll cycle[N];
int f[N];
int n, k;
int t = 1;
ll ans = 1;

int search_cycle(int start){
    int curr = start;
    while (1){
        if (visit[curr] != 0 && visit[curr] < visit[start])
            return 0;
        else if (visit[curr] != 0)
            return t - visit[curr];
        visit[curr] = t++;
        curr = f[curr];
    }
}

int main(){
    //freopen("input.txt", "r", stdin);
    scanf("%d %d", &n, &k);

    for (int i = 1; i <= n; i++){
        scanf("%d", &f[i]);
    }
    cycle[0] = 1;
    cycle[1] = k;
    cycle[2] = cycle[1]* (k - 1) % mod;
    cycle[3] = cycle[2] * (k - 2) %mod;
    for (int i = 4; i <= n; i++){
        cycle[i] = (((k - 2)*cycle[i - 1] % mod) + ((k - 1)*cycle[i - 2] % mod)) % mod;
    }

    int total_cycle = 0;
    for (int i = 1; i <= n; i++){
        if (visit[i] == 0){
            int c = search_cycle(i);
            ans = (ans * cycle[c]) % mod;
            total_cycle += c;
        }
    }

    for (int i = 0; i < n - total_cycle; i++){
        ans = ans* (k - 1) % mod;
    }

    printf("%lld", ans);

    return 0;
}