#1988. 怀旧
怀旧
怀旧
题目描述
标题: 怀旧 - Problem - QOJ.ac
#21427. 怀旧
The problem was used in the following contests:
你可以回去,但那里已经没有人了。
题目描述
有一个长度为 n 的排列 a,初始时对于所有 1≤i≤n,均有 ai=i。
依次对 x=1,2,⋯,n 执行如下操作:在 1∼n 中等概率地随机选择一个整数 y,交换 ax 与 ay。每次选择相互独立,允许 y=x。
给定一个长度为 n 的排列 b,请计算上述 n 次操作全部结束后,a 与 b 完全相同的概率。答案对 998244353 取模。
设该概率写成既约分数 pq,你需要输出唯一的整数 r,满足 0≤r<998244353 且 qr≡p(mod998244353)。可以证明,在本题的数据范围内,r 一定存在。
输入格式
第一行包含一个整数 n。
第二行包含 n 个整数 b1,b2,⋯,bn,表示给定的排列。
输出格式
输出一行一个整数,表示所求概率对 998244353 取模的结果。
样例 1
输入
3
2 3 1
输出
406692144
解释
三次随机选择共有 33=27 种等可能的结果,其中 5 种得到排列 [2,3,1],故所求概率为 5/27。
样例 2
输入
7
3 2 6 5 4 7 1
输出
711069236
样例 3
见附件中 nostalgia3.in 与 nostalgia3.ans。该样例满足子任务 3 的约束条件。
样例 4
见附件中 nostalgia4.in 与 nostalgia4.ans。该样例满足子任务 4 的约束条件。
样例 5
见附件中 nostalgia5.in 与 nostalgia5.ans。该样例满足子任务 5 的约束条件。
样例 6
见附件中 nostalgia6.in 与 nostalgia6.ans。该样例满足子任务 6 的约束条件。
数据范围
本题开启合理的子任务依赖。
子任务 n≤ 特殊性质 分值 1 7 无 7 2 20 19 3 40 A 21 4 B 23 5 C 12 6 无 18
将每个位置 i 向 bi 连一条有向边,会得到一个由若干个互不相交的有向环组成的图。
特殊性质 A:上述图恰好由一个环组成。
特殊性质 B:上述图由至多两个环组成。
特殊性质 C:对于所有 1≤i≤n,均有 bi=i。
对于所有数据,1≤n≤40,保证 b 是一个长度为 n 的排列。
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
3
2 3 1
406692144
样例 2
7
3 2 6 5 4 7 1
711069236