相关链接
题目传送门:http://oi.cyo.ng/wp-content/uploads/2017/07/NOI2017-matthew99.pdf
解题报告
从$i$向$a_i$连边
不难发现这题就是求一个基环树森林与自身同构的情况
这个我们可以用$Hash$来搞一搞
Code
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 1000009; const int MOD = 1000000007; const int INF = 2e9; int n, E, ans, head[N], nxt[N], to[N]; int inv[N], pw[N], ipw[N], pw23[N], R1[N], R2[N]; int pre[N], dep[N], in[N], deg[N], vis[N]; inline int read() { char c = getchar(); int ret = 0, f = 1; for (; c < '0' || c > '9'; c = getchar()) { f = c == '-'? -1: 1; } for (; '0' <= c && c <= '9'; c = getchar()) { ret = ret * 10 + c - '0'; } return ret * f; } inline int Pow(int w, int t) { int ret = 1; for (; t; t >>= 1, w = (LL)w * w % MOD) { if (t & 1) { ret = (LL)ret * w % MOD; } } return ret; } inline void AddEdge(int u, int v) { in[v]++; deg[v]++; pre[u] = v; to[++E] = u; nxt[E] = head[v]; head[v] = E; } inline void mrk(int w) { vis[w] = 1; if (--in[pre[w]] == 0) { mrk(pre[w]); } } inline int cal_node(int w) { int ret = R2[deg[w]]; vector<int> arr; for (int i = head[w]; i; i = nxt[i]) { if (!in[to[i]]) { dep[to[i]] = dep[w] + 1; int tmp = cal_node(to[i]); arr.push_back(tmp); ret = (ret + (LL)R1[dep[w]] * tmp) % MOD; } } sort(arr.begin(), arr.end()); for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) { for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j); ans = (LL)ans * ipw[j - i + 1] % MOD; } return (LL)ret * ret % MOD; } inline int cal_cir(int w) { vector<int> node, arr; while (!vis[w]) { vis[w] = 1; node.push_back(w); for (int i = head[w]; i; i = nxt[i]) { if (in[to[i]]) { w = to[i]; break; } } } for (int i = 0; i < (int)node.size(); i++) { dep[node[i]] = 6; arr.push_back(cal_node(node[i])); } int sta = 0, cnt = 1; for (int i = 0; i < (int)node.size(); i++) { sta = (sta + (LL)pw23[i] * arr[i]) % MOD; } int ret = (LL)sta * pw23[n] % MOD; for (int i = 1, cur = sta; i < (int)node.size(); i++) { cur = (cur + (LL)arr[i - 1] * (pw23[i - 1 + node.size()] - pw23[i - 1])) % MOD; ret = min(ret, int((LL)cur * pw23[n - i] % MOD)); cnt += ((cur = (cur + MOD) % MOD) == (LL)sta * pw23[i] % MOD); } ans = (LL)ans * inv[cnt] % MOD; return ret; } int main() { srand(19991216); inv[0] = pw[0] = ipw[0] = pw23[0] = 1; R1[0] = rand(); R2[0] = rand(); for (int i = 1; i < N; i++) { pw[i] = (LL)pw[i - 1] * i % MOD; pw23[i] = pw23[i - 1] * 131ll % MOD; inv[i] = Pow(i, MOD - 2); ipw[i] = Pow(pw[i], MOD - 2); R1[i] = rand(); R2[i] = rand(); } for (int T = read(); T; T--) { memset(head, 0, sizeof(head)); memset(deg, 0, sizeof(deg)); memset(vis, 0, sizeof(vis)); memset(in, 0, sizeof(in)); E = 0; ans = 1; n = read(); for (int i = 1; i <= n; i++) { AddEdge(i, read()); } for (int i = 1; i <= n; i++) { if (!in[i] && !vis[i]) { mrk(i); } } vector<int> arr; for (int i = 1; i <= n; i++) { if (in[i] && !vis[i]) { arr.push_back(cal_cir(i)); } } sort(arr.begin(), arr.end()); for (int i = 0, j = 0; i < (int)arr.size(); i = j + 1) { for (; j + 1 < (int)arr.size() && arr[i] == arr[j + 1]; ++j); ans = (LL)ans * ipw[j - i + 1] % MOD; } ans = ((LL)ans * pw[n] - 1) % MOD; printf("%d\n", (ans + MOD) % MOD); } return 0; }