小红的部分不同字符串

1. 题目概述

一个长度为 n 的字符串仅由 26 个小写英文字母组成。 n 个限制条件,用一个数组 a = {a₁, a₂, …, aₙ} 表示,意为第 i 个字符与第 aᵢ 个字符不同。 求有多少种不同的字符串满足以上限制。对 998244353 取模

2. 输入数据范围

2 ≦ n ≦ 2e5, 1 ≦ aᵢ ≦n且aᵢ != i

3. 关键思考

并查集建图,各连通块处理着色问题;注意一共n个点n条边,所以全部连通块成基环形式,拓扑排序找树枝,剩下的就是环,然后ksm计数

4. 如何实现

新奇的点在于对每个块做拓扑排序可以找出非环点,因为环上的点无法被push进去

5. 标签

并查集 着色计数 缩点思想 拓扑排序->找非环点

6. 原题跳转

点击前往原题
← 返回题库首页