CF1863G Swaps 做题记录

给定长度为 $n$ 的序列 $a$，每次操作可以选定一个 $i$，并 $\operatorname{swap}(a_i,a_{a_i})$。求能通过进行任意次这种操作得到的不同序列数。

$n\le 10^6$。

不妨称能经过若干次操作得到的序列为合法序列。

看到这个操作形式可以想到建立一个 $n$ 个点的图 $G$ 且从 $i$ 向 $a_i$ 连一条有向边。那么 $G$ 一定是一棵内向基环树。

那么发现一次操作相当于：

那么对于一个固定的 $i$，操作若干次相当于：

设 $i$ 最后指向的点为 $p_i$，显然 $p_i$ 一定是 $i$ 的某个祖先。则不难发现 $G$ 中每个点会且仅会被一条 $[i,p_i)$ 的链（$i\to p_i$ 的去掉 $p_i$ 的路径）包含，那么每一个 $G$ 的链剖分方案都能对应一个合法序列（不一定是一一对应，一个合法序列有可能对应多个链剖分方案）：

设 $son_u=\sum\limits_{i=1}^n [a_i=u]$ 即 $u$ 的儿子个数，那么显然 $G$ 的链剖分方案个数就是 $\prod\limits_{i=1}^n son_i+1$ 即每个点可以选一个儿子的链接上或者不接。

对于树的情况，容易发现链剖分方案和合法序列一一对应。但是由于是基环树，所以会出现这种情况：

也就是绕了一圈回来了。

不难证明只有这种情况不合法，那么减掉这种链剖分的个数 $\sum\limits_{i=1}^n [i\in cir]son_{i}\times \prod\limits_{i=1}^n[i\notin cir](son_i+1)$ 即可（在环上的每个点都可以选择某个儿子的链接上再绕一圈，不在环上的点不影响）。

时间复杂度 $O(n)$，代码如下：

#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>

using namespace std;

const int S=1000005,p=1000000007;

int fra[S];
int n,a[S];
vector<int> g[S];
int ind[S];
int son[S],fa[S];
int siz[S],res[S],ans[S];

int fnd(int x)
{
	return fa[x]==x?x:fa[x]=fnd(fa[x]);
}

int main()
{
	fra[0]=1;
	for(int i=1;i<=S-3;i++) fra[i]=1ll*fra[i-1]*i%p;
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) g[i].push_back(a[i]),ind[a[i]]++;
	queue<int> q;
	for(int i=1;i<=n;i++) if(ind[i]==0) q.push(i);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int v:g[u]) if(--ind[v]==0) q.push(v);
	}
	for(int i=1;i<=n;i++) son[a[i]]++,fa[i]=i;
	for(int i=1;i<=n;i++) fa[i]=fnd(a[i]);
	for(int i=1;i<=n;i++) siz[i]=0,res[i]=ans[i]=1;
	for(int i=1;i<=n;i++)
	{
		int ri=fnd(i);
		if(ind[i]==0) res[ri]=1ll*res[ri]*(son[i]+1)%p;
		else siz[ri]+=son[i],ans[ri]=1ll*ans[ri]*(son[i]+1)%p;
	}
	int val=1;
	for(int i=1;i<=n;i++)
	{
		if(fa[i]!=i) continue;
		val=1ll*val*((ans[i]-siz[i])%p+p)%p*res[i]%p;
	}
	printf("%d\n",val);
	return 0;
}