CF1863G Swaps 题解

zrl123456 · 2025-11-21 10:48:57 · 题解

:::::info[闲话] ::::: :::::info[题目基本信息] 考察：基环树，组合数学，Ad-hoc（2800）。
题目简介：
给定序列 \{a_n\}，你可以进行若干次下面的操作：

• 选择一个 i\in[1,n]，交换 a_i 和 a_{a_i}。

问最终能得到的序列个数对 10^9+7 取模的结果。
数据范围：

• 1\le n\le 10^6
• \forall i\in[1,n],1\le a_i\le n

  ::::: 闲话里已经透露了，套用经典建图 trick，我们可以建图连边，连出 i\rightarrow a_i 的一条边，形成了一个 n 个点 n 条边的内向基环树森林。
  我们考虑观察操作前后图的变化，原来的图有 i\rightarrow a_i\rightarrow a_{a_i}，现在操作后交换了 a_i 和 a_{a_i}（下文简称操作 a_i），那么变成了 i\rightarrow a_{a_i} 以及 a_i\rightarrow a_i。
  我们观察到若一个点连成了一个自环，那么再次操作它会无效，我们为方便最后的计数钦定不能再操作这个点。
  但是我们观察到图的改变会对我们的计数带来很大的麻烦，所以我们不妨不改变图的形态，只给 i\rightarrow a_i 这条边打一个标记，那么通过标记我们能否还原最终的 \{a_n\} 序列？
  答案是肯定的：

• 若点 u 存在一条入边被打标记，那么点 u 已经被操作过，a_u=u。
• 否则，我们从点 u 开始，不断走它的出边，直到找到一条没有被打标记的边，它的出点 v 就是 a_u。

容易发现每个合法标记序列能够唯一映射到一个 \{a_n\} 序列，由于每个点最多有一条入边被打标记那么答案上界就是 \displaystyle\prod_{i=1}^nind_i+1，其中 ind_i 是 i 点的入度。
那么这是否就是答案？
这并不是。
举个例子，一个环上的边全部标记就不合法，因为你在打最后一条边的标记时 a_u 已经全部等于 u，无法再操作，也就是说一个环上只有一条边未被操作时不能再对环上的点进行操作了，那么枚举环上的点 u，操作 u 的可能性有 ind_u 种，那么可能就会有 \displaystyle\sum_{u}ind_u 种不合法的标记序列了。
那么最终我们就得到了答案的式子：

这样我们就做完了这道题。
时空复杂度均为 \Theta(n)。

code