#PQJ4586x21427. QOJ 4586_21427

    ID: 2972 传统题 1000ms 1024MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:集训队赛事:IOI 2027 互测组合数学数论

QOJ 4586_21427

标题: 怀旧 - Problem - QOJ.ac

#21427. 怀旧

Statistics

The problem was used in the following contests:

你可以回去,但那里已经没有人了。

蓬莱传说 - ZUN

题目描述

有一个长度为 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 的排列。