一道计数题

· · 个人记录

一道计数题

给定一个长度为 n 的序列 a_i, 每次可以选定一个 i 并执行 {\rm swap(a_i, a_{a_i})}, 问能够得到的本质不同的 a_i 数量.

--- 考虑一张图, 编号为 $i$ 的点向 $a_i$ 连单向边. 自环不显示在这张图上. 则图为内向树森林和内向基环树森林. 那么原题操作相当于将 $(i, j)$ 和 $(j, k)$ 变为 $(i, k)$. 考虑内向树森林的部分. 对于一个非根点 $x$ 和它的所有儿子 $Son_x$, 所有儿子都能断掉 $x$ 到父亲的边并改为自己连上去, 则有 $|Son_x| + 1$ 种方式为父亲送上一个点. 故方案数为 $\prod_{x \neq Root} (|Son_x| + 1)$. 考虑内向基环树森林的部分. 发现可以用同样的方法将图消成只有一个环 $C$ 和周围一圈点 $Son$ (即只剩深度 $\le$ 2 的点) 的图, 后称太阳树. 重新考虑转化后的操作, 相当于可以将环上一个点移除环并保持环的连接方式 (胞吞?). 或者将一个环点 $x$ 的一个儿子移动到 $x$ 的后继的儿子, 同时断开 $x$ 到后继的边. (就是分类讨论操作中的 $i$ 是否在环上) 发现第一种操作对图的影响较小, 假设我们只能进行第二种操作. 枚举断开的环边集合 $E \subseteq C$, 若认为一个儿子不能连续移动, 则方案数为 $\prod_{(x, y) \in E} |Son_x|$, 若能连续移动, 则对于一个两侧的边都被删了的点 $x$, 贡献从 $|Son_x|$ 改为 $(|Son_x| + 1)$. 进一步地, 对于不能连续移动的情况, 所有情况的和即为 $\prod_{(x, y) \in C} (|Son_x| + 1)$ (要么断开要么不断). 事实上, 当不能进行第一种操作时计算方案数应该认为能够连续移动, 但我们先不管. 现在我们能够进行第一种操作. 考虑将一个点 $x$ 移除后, 对 $x$ 的前驱进行第二种操作, 则相当于对 $x$ 的前驱做第二次操作, 移动之后再对 $x$ 操作这个儿子 (即移动到 $x$ 后继). 为了去重, 可以认为不能连续移动. 恰好能够做到去重. 但是, 相较于上面列出的式子, 现在多了一个选择是进行第一种操作. 故答案为 $\prod_{(x, y) \in C} (|Son_x| + 2)$. 还没完, 假设对 $|C| - 1$ 个点都进行了第一种操作, 那么事实上与对 $|C|$ 个点都进行第一种操作是本质相同的. 故需要将这部分减去. 对于一个点 $x$, 若只有它没有被进行第一种操作, 那么断开的贡献是 $|Son_x|$, 不断的贡献是 1, 则需要减 $|C| + \sum_{x \in C} |Son_x|$. 发现最终的式子适用于内向树森林, 则不用特判了. 因此, 先把图变成太阳树森林, 需要乘上 $\prod_{x \notin AnyC} (|Son_x| + 1)$, 然后对于每个连通块使答案额外乘上 $\prod_{(x, y) \in C} (|Son_x| + 2) - |C| - \sum_{x \in C} |Son_x|$. $O(n)$.