CF1863G Swaps
樱雪喵
·
·
题解
Description
给定长度为 n 的序列 a，每次操作可以选定一个 i，并 \operatorname{swap}(a_i,a_{a_i})。求能通过某种操作顺序得到的不同序列数。
## Solution
思路来自 [官方题解](https://codeforces.com/blog/entry/119902)。
考虑建图。对于每个 $i$，连边 $i \to a_i $。则构造出一个 $n$ 个点 $n$ 条边的图，且每个点有且仅有一条出边。
定义操作 $\operatorname{swap}(a_i,a_{a_i})$ 为“操作点 $i$”。观察对点 $i$ 进行操作后图的变化（不考虑环），发现原图从 $i\to a_i \to a_{a_i}$ 变为 $i\to a_{a_i},a_i\to a_i$。对于交换后不改变序列的情况，形如 $u\to v\to v$，则操作不合法。由于每次操作都对图的结构进行改动不好处理，我们换一种方式，对 $i \to a_i$ 这条边打个标记来表示对 $i$ 进行了一次操作。
假设当前局面的点 $i$，分为两种情况：
- 点 $i$ 存在一条入边被标记，那实际上的序列里 $i$ 已经是自环了，不能再操作；
- 点 $i$ 不存在入边被标记，那么我们顺着 $i$ 的出边走，直到找到**第一条未被标记**的边，把它打上标记。
完成操作后，对于一个给定的标记集合，可以用如下方式构造出实际序列：
- 若点 $i$ 存在入边被标记，$a_i=i$;
- 否则，$a_i$ 的实际值为 沿着 $i$ 的出边走，第一条未被标记的边 指向的点。
对边的标记集合进行计数。设每个点的入度为 $in_i$，且每个点至多有一条入边被标记，则总方案数为 $\prod\limits_{i=1}^n (in_i+1)$。
但不是所有满足这个条件的标记集合都是合法的。考虑图中存在环的情况，并不能构造出一种方案，使这个环的所有边都被标记。因为这个环在只剩一条边未被标记时，实际的序列就已经所有 $a_i=i$ 了。
这同时启发我们发现，对于一个环只有一条边未标记的情况，无论哪条边不被标记，生成的序列都是一样的。那么对于长度为 $k$ 的环 $c_1,c_2,\dots,c_k$，恰有一条边未被标记的方案数有 $\sum\limits_{i=1}^k in_{c_i}$ 种，合法且不重复的方案数为：
$$\prod_{i=1}^k (in_{c_i}+1) -[(\sum_{i=1}^k in_{c_i})-1]-1=\prod_{i=1}^k (in_{c_i}+1) -\sum_{i=1}^k in_{c_i}$$
则总方案数为：
$$\prod_{\operatorname{cycles}}(\prod_{i=1}^k (in_{c_i}+1) -\sum_{i=1}^k in_{c_i})\cdot\prod_{\operatorname{other\ v}}(in_v+1)$$
```cpp
const int N=1e6+5,mod=1e9+7;
int n,a[N],in[N];
int ans=1,flag[N],tot,t[N],instk[N],vis[N];
void dfs(int now)
{
if(vis[now]) return;
vis[now]=1,instk[now]=1,t[++tot]=now;
if(instk[a[now]])
{
int res=1,sum=0;
for(int i=tot;i;i--)
{
flag[t[i]]=1;
res=1ll*res*(in[t[i]]+1)%mod,sum=(sum+in[t[i]])%mod;
if(t[i]==a[now]) break;
}
ans=1ll*ans*(res-sum)%mod;
}
else dfs(a[now]);
tot--,instk[now]=0;
}
int main()
{
n=read();
for(int i=1;i<=n;i++) a[i]=read(),in[a[i]]++;
for(int i=1;i<=n;i++) dfs(i);
for(int i=1;i<=n;i++) if(!flag[i]) ans=1ll*ans*(in[i]+1)%mod;
printf("%d\n",(ans+mod)%mod);
return 0;
}
/*
8
3 3 3 1 1 5 7 3
*/
```