LFYZOJ 104 Counting Swaps

题解
#include <iostream>

#include <cstdio>

#include <algorithm>

#include <cmath>

#include <cstring>

#define ll long long

using namespace std;

const int MOD = 1e9 + 9, MAXN = 100005;

int T, n, num[MAXN], head[MAXN], nume, id[MAXN], hav[MAXN];

ll fac[MAXN], ni[MAXN];

struct edge{

	int to, nxt;

}e[MAXN<<1];

void adde(int from, int to) {

	e[++nume].to = to;

	e[nume].nxt = head[from];

	head[from] = nume;

}

ll quick_mod(ll a, ll k) {

	if(!a) return 0ll;

	if(k <= 0) return 1ll;

	ll ans = 1;

	while(k) {

		if(k & 1ll) (ans *= a) %= MOD;

		(a *= a) %= MOD;

		k >>= 1;

	}

	return ans % MOD;

}

void dfs(int u, int cur) {

	id[u] = cur;

	for(int i = head[u]; i; i = e[i].nxt) {

		int v = e[i].to;

		if(!id[v]) dfs(v, cur);

	}

}

int main() {

	cin >> T;

	fac[0] = 1;

	for(int i = 1; i <= 100000; i++) fac[i] = fac[i - 1] * i % MOD;

	ni[100000] = quick_mod(fac[100000], MOD - 2);

	for(int i = 100000 - 1; i >= 0; i--) (ni[i] = ni[i + 1] * (i + 1)) %= MOD;

	while(T--) {

		cin >> n;

		memset(head, 0, sizeof(head));

		memset(id, 0, sizeof(id));

		memset(hav, 0, sizeof(hav));

		nume = 0;

		for(int i = 1; i <= n; i++) scanf("%d", &num[i]), adde(i, num[i]);

		int cnt = 0;

		for(int i = 1; i <= n; i++) if(!id[i]) dfs(i, ++cnt);

		for(int i = 1; i <= n; i++) hav[id[i]]++;

		ll ans = 1ll;

		for(int i = 1; i <= cnt; i++) (ans *= quick_mod(hav[i], hav[i] - 2)) %= MOD;

		(ans *= fac[n - cnt]) %= MOD;

		for(int i = 1; i <= cnt; i++) (ans *= ni[hav[i] - 1]) %= MOD;

		printf("%lld\n", ans);

	}

	return 0;

}
巴特西

LFYZOJ 104 Counting Swaps

最新文章

热门文章
