#P18753. [2027年国家集训队互测] Nostalgia

    ID: 18089 传统题 1000ms 1024MiB 尝试: 1 已通过: 1 难度: 10 上传者: 标签>CF3400NOI/NOI+/CTS功能图置换循环分解区间 DP前缀和优化 DP计数 DP子集 DP重复元素除重倒序更新避免重复使用模逆元

[2027年国家集训队互测] Nostalgia

Nostalgia

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

蓬莱传说 - ZUN

题目描述

有一个长度为 nn 的排列 aa,初始时对于所有 1≤i≤n1\le i\le n,均有 ai=ia_i=i。

依次对 x=1,2,⋯ ,nx=1,2,\cdots,n 执行如下操作:在 1∼n1\sim n 中等概率地随机选择一个整数 yy,交换 axa_x 与 aya_y。每次选择相互独立,允许 y=xy=x。

给定一个长度为 nn 的排列 bb,请计算上述 nn 次操作全部结束后,aa 与 bb 完全相同的概率。答案对 998244353998244353 取模。

设该概率写成既约分数 pq\frac{p}{q},你需要输出唯一的整数 rr,满足 0≤r<9982443530\le r<998244353 且 qr≡p(mod998244353)qr\equiv p\pmod{998244353}。可以证明,在本题的数据范围内,rr 一定存在。

输入格式

第一行包含一个整数 nn。

第二行包含 nn 个整数 b1,b2,⋯ ,bnb_1,b_2,\cdots,b_n,表示给定的排列。

输出格式

输出一行一个整数,表示所求概率对 998244353998244353 取模的结果。

样例 1

样例输入

3
2 3 1

样例输出

406692144

解释

三次随机选择共有 33=273^3=27 种等可能的结果,其中 55 种得到排列 [2,3,1][2,3,1],故所求概率为 5/275/27。

样例 2

样例输入

7
3 2 6 5 4 7 1

样例输出

711069236

样例 3

样例输入 #3

40
6 5 32 13 38 30 16 22 21 23 33 14 3 2 4 27 34 11 39 28 7 19 12 37 29 1 36 18 9 8 15 26 35 24 25 10 20 40 17 31

样例输出 #3

509272668

见附件中 nostalgia3.in 与 nostalgia3.ans。该样例满足子任务 3 的约束条件。

样例 4

样例输入 #4

40
10 24 33 22 15 39 31 13 36 26 5 9 3 34 14 17 7 23 28 2 35 27 4 32 18 21 37 40 11 19 20 1 25 8 38 6 29 30 16 12

样例输出 #4

877710786

见附件中 nostalgia4.in 与 nostalgia4.ans。该样例满足子任务 4 的约束条件。

样例 5

样例输入 #5

40
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

样例输出 #5

19887849

见附件中 nostalgia5.in 与 nostalgia5.ans。该样例满足子任务 5 的约束条件。

样例 6

样例输入 #6

40
24 18 39 35 28 32 40 11 34 4 8 30 19 37 36 29 9 2 22 21 38 13 27 31 12 3 23 5 16 25 1 6 7 17 10 15 14 20 26 33

样例输出 #6

813888012

见附件中 nostalgia6.in 与 nostalgia6.ans。该样例满足子任务 6 的约束条件。

数据范围

本题开启合理的子任务依赖。

子任务 n≤n\le 特殊性质 分值
11 77 无 77
22 2020 1919
33 4040 A 2121
44 B 2323
55 C 1212
66 无 1818

将每个位置 ii 向 bib_i 连一条有向边,会得到一个由若干个互不相交的有向环组成的图。

特殊性质 A:上述图恰好由一个环组成。

特殊性质 B:上述图由至多两个环组成。

特殊性质 C:对于所有 1≤i≤n1\le i\le n,均有 bi=ib_i=i。

对于所有数据,1≤n≤401\le n\le 40,保证 bb 是一个长度为 nn 的排列。

子任务表

样例附件