AcWing 212. 计数交换
原题链接
简单
作者:
Tizzi
,
2019-11-11 21:37:28
,
所有人可见
,
阅读 930
C++ 代码
#include <cstdio>
#include <iostream>
#include <cstring>
typedef long long ll;
using namespace std;
const int M = 1e9 + 9, N = 1e5 + 5;;
int F[N], jc[N], p[N], vis[N];
int qpow(int a, int b) {
int ans = 1;
while (b) {
if (b & 1) {
ans = (ll)ans * a % M;
}
a = (ll)a * a % M;
b >>= 1;
}
return ans;
}
void init() {
jc[0] = jc[1] = 1;
F[0] = F[1] = 1;
for (int i = 2; i < N; i++) {
F[i] = qpow(i, i - 2) % M;
jc[i] = (ll)jc[i - 1] * i % M;
}
}
int main() {
init();
int t, n;
scanf("%d", &t);
while (t--) {
memset(vis, 0, sizeof(vis));
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
scanf("%d", p + i);
}
int ans = 1;
int k = 0; //环的个数
//求出长度为len的环
for (int i = 1; i <= n; i++) {
if (vis[i]) continue;
//否则求出长度
int len = 1;
//从自环的起点出发若回到起点结束
for (int j = p[i]; j != i; j = p[j]) {
len++;
vis[j] = 1; //标记为访问过 下次就不求这个环了
}
k++;
//根据书上推导的公式
ans = (ll)ans * F[len] % M * qpow(jc[len - 1], M - 2) % M;
}
ans = (ll)ans * jc[n - k] % M;
printf("%d\n", ans);
}
return 0;
}