9521번: PALETA

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

fi <- i를 모두 연결해보면 트리나 하나의 사이클에 트리가 달린 그래프만 존재한다.
만약 모든 사이클에 채색을 마쳤다면 나머지 노드들에게는 각각 k-1가지의 채색 방법이 존재한다.
따라서 답은 각 사이클 채색 수 곱 * (k-1)^나머지 노드 수이다.
사이클 채색은 위키피디아 참조
https://en.wikipedia.org/wiki/Graph_coloring#Chromatic_polynomial

아래 소스의 시간복잡도는 $O(n)$

#include<cstdio>
#define mod (int(1e9)+7)
int n, k, a[1000001], vis[1000001], s, c;
long long r = 1, dp[1000001];
int main() {
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++) scanf("%d", a + i);
    dp[0] = k;
    for (int i = 2; i <= n; i++) dp[i] = (dp[i - 1] * (k - 2) + dp[i - 2] * (k - 1)) % mod;
    dp[1] = k;
    for (int i = 1; i <= n; i++) if (!vis[i]) {
        int j = i;
        while (!vis[j]) vis[j] = ++c, j = a[j];
        if (vis[j] >= vis[i]) r = r*dp[c - vis[j] + 1] % mod, s += c - vis[j] + 1;
    }
    for (int i = n - s; i--;) r = r*(k - 1) % mod;
    printf("%lld", r);
    return 0;
}