开始认为是并查集，但是看到不等于觉得不好传递，于是就搁下了。事后发现这是道只要去好好想，就能做的题。
题意：\(n\) 个数，\(i\) 与 \(f_i\) 颜色不同，\(k\) 色，求方案数。
把连边的图建出来。这是基环树与树组成的森林。
对于一棵树，拉一个点做根，或者说，大小为 \(1\) 的环。其它点各有 \(k-1\) 种染法。总方案就是 \(k \cdot (k-1)^{n-1}\)，\(n\) 为树上点数。
对于基环树，把环拉出来做根。其它点都是 \(k-1\) 种。而环的染法是经典小奥。
设现在考虑 \(n\) 个点，\(k\) 种颜色的环的染色。不妨认为 \(k\) 是定值，因为在实际处理中，\(k\) 一般只是参数的位置。
考虑第 \(n\) 个位置，设值为 \(f_n\)：
-
\(a_1=a_{n-1}\)。合并第 \(1\) 个位置和第 \(n-1\) 个位置，贡献为 \((k-1) \cdot f_{n-2}\)
-
\(a_1 \neq a_{n-1}\)。情况即为 \(n-1\) 时的情况，贡献为 \((k-2) \cdot f_{n-1}\)
迭代实现即可。
#include <cstdio>
#include <queue>
#include <vector>
using namespace std;
const int M = 1000005, mod = 1000000007;
int qpow(int a, int b) {int ans = 1; for(; b; b >>= 1) {if(b & 1) ans = 1ll * ans * a % mod; a = 1ll * a * a % mod;} return ans;}
int n, k, ans = 1, tim, calc[M], f[M], dfn[M], cnt, ss, cnt2;
int top;
int dfs(int x){
int xx = x;
for(; ;){
// if(f[x] == x) return 1;
if(dfn[x]) return dfn[x] >= dfn[top] ? cnt - dfn[x] + 1 : 0;
dfn[x] = ++cnt; x = f[x];
}
}
void work(int x){
top = x; int siz = dfs(x);
if(siz > 0){
ans = 1ll * ans * calc[siz] % mod; ss += siz;
}
}
int main(){
scanf("%d %d", &n, &k);
calc[0] = 1; calc[1] = k; calc[2] = 1ll * k * (k-1) % mod; calc[3] = 1ll * k * (k-1) * (k-2) % mod;
for(int i = 4; i <= n; i++){
calc[i] = (1ll * (k-1) * calc[i-2] % mod + 1ll * (k-2) * calc[i-1] % mod) % mod;
}
for(int i = 1; i <= n; i++) {
scanf("%d", &f[i]);
}
for(int i = 1; i <= n; i++) if(!dfn[i]) work(i);
// printf("%d %d\n", ans, ss);
printf("%d\n", 1ll * ans * qpow(k-1, n-ss) % mod);
}