[雅礼1706 Day 5] 学外语

一个长度为 n 的序列 a, 每个元素是不超过 n 的正整数. 一次操作: 选择两个不超过 n 的正整数 x,y, 交换 a[x],a[y], 再把序列中所有 x 改成 y, 所有 y 改成 x. 操作可以进行任意次. 问能生成多少个不同的新序列, 模 10^9+7. (1≤数据组数T≤30, 1≤n≤10^5) 遇到奇怪的操作, 得想想这实际上是在干什么......

设 . 该操作先交换了 , 后交换了 .

如果 , 则称 指向 . 那么, 一次操作先交换了 指向的元素, 后交换了指向 的元素. 从 向 连一条有向边, 那么这个操作在交换 节点的编号!

当然这对于阅读本文的您可能很显然......>_< 考试的时候没想到要考虑一下图论模型啊.

给一个基环内向树森林, 可以给节点任意标号为1~n, 求本质不同的带标号图的数目 (当然, 减1再输出). 也就是和原图同构的图的数目.

如果不考虑本质不同, 有 个图. 有 棵同构的子树, 答案除以 ; 长度为 的环 (每个节点是一棵树) 最小循环节为 , 答案除以 ; 棵相同的基环树, 答案除以 .

可以用树哈希判断两棵树是否同构. 怎样选择一个好的哈希函数呢? 奥妙重重......个人觉得直接把括号序列哈希是个不错的选择.

找循环节也可以哈希~ 把环看成字符串, 求出以每个位置为起点的哈希值. 转得和原来相等的最小偏移量即为最小循环节.

把环最小的哈希值作为整棵基环树的哈希值.

就是这样, 喵~

// c++11 required
#define size(x) (int)x.size()

using namespace std;

typedef unsigned long long ull;
typedef pair<ull, int> P;

const int MOD = 1e9 + 7, N = 1e5 + 1;
const ull hash_p = 103237;

ull fpm(ull x, ull n)
{
	ull y = 1;
	for (; n; n >>= 1, (x *= x) %= MOD)
		if (n & 1)
			(y *= x) %= MOD;
	return y;
}

vector<int> adj[N], cir;
unordered_map<ull, int> F;
bool on[N];
ull ans, h[N], H[N], pw[N], pw3[N];
int n, now, vis[N], fa[N], fac[N], ifac[N], inv[N];

void init()
{
	fac[0] = 1;
	rep (i, 1, N) fac[i] = 1LL * fac[i-1] * i % MOD;
	ifac[N-1] = fpm(fac[N-1], MOD-2);
	per (i, N-1, 1) ifac[i-1] = 1LL * ifac[i] * i % MOD;
	rep (i, 1, N) inv[i] = 1LL * ifac[i] * fac[i-1] % MOD;
	pw[0] = pw3[0] = 1;
	rep (i, 1, N) pw[i] = pw[i-1] * hash_p;
	rep (i, 1, N) pw3[i] = pw3[i-1] * 5;
}

void find_circle(int u)
{
	vis[u] = now;
	for (auto v : adj[u])
	{
		if (vis[v])
		{
			if (vis[v] != now) continue;
			int p = u;
			while (p != v)
			{
				on[p] = true;
				cir.push_back(p);
				p = fa[p];
			}
			on[p] = true;
			cir.push_back(p);
		}
		else
		{
			find_circle(v);
		}
	}
}

int process_tree(int u)
{
	vector<P> tmp;
	for (auto v : adj[u])
	{
		if (on[v]) continue;
		int t = process_tree(v);
		tmp.push_back(P(h[v], t));
	}
	sort(tmp.begin(), tmp.end());
	h[u] = 1;
	int z = 1;
	for (int i = 0, j = 0; i < size(tmp); i = j)
	{
		while (j < size(tmp) && tmp[j] == tmp[i])
		{
			h[u] += tmp[j].first * pw3[z];
			z += tmp[j].second;
			++j;
		}
		ans = ans * ifac[j-i] % MOD;
	}
	h[u] += 2 * pw3[z];
	return z;
}

void process_circle()
{
	static ull tmp[2*N];
	
	for (auto v : cir)
		process_tree(v);
	
	int s = size(cir);
	cir.resize(s * 2);
	copy(cir.begin(), cir.begin() + s, cir.begin() + s);
	
	tmp[2*s] = 0;
	per (i, 2*s-1, 0)
		tmp[i] = tmp[i+1] * hash_p + h[cir[i]];
	
	rep (i, 0, s)
		H[i] = tmp[i] - tmp[i+s] * pw[s];

	++F[*min_element(H, H+s)];
	
	rep (t, 1, s)
		if (H[t] == H[0])
		{
			ans = ans * inv[s/t] % MOD;
			break;
		}
}

void process_forest()
{
	memset(vis, 0, sizeof(int) * n);
	memset(on, 0, sizeof(bool) * n);
	F.clear();
	now = 0;
	ans = fac[n];
	
	rep (i, 0, n)
	{
		if (vis[i]) continue;
		cir.clear();
		++now;
		find_circle(i);
		if (!cir.empty()) process_circle();
	}
	for (auto p : F)
		ans = ans * ifac[p.second] % MOD;
}

int main()
{
	init();
	int T;
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d", &n);
		rep (i, 0, n) adj[i].clear();
		rep (i, 0, n)
		{
			scanf("%d", fa+i);
			adj[--fa[i]].push_back(i);
		}
		process_forest();
		printf("%llu\n", (ans + MOD - 1) % MOD);
	}
	fprintf(stderr, "%f\n", (double)clock()/CLOCKS_PER_SEC);
	return 0;
}