#P18753. [2027年国家集训队互测] Nostalgia
[2027年国家集训队互测] Nostalgia
Nostalgia
你可以回去,但那里已经没有人了。
蓬莱传说 - ZUN
题目描述
有一个长度为 的排列 ,初始时对于所有 ,均有 。
依次对 执行如下操作:在 中等概率地随机选择一个整数 ,交换 与 。每次选择相互独立,允许 。
给定一个长度为 的排列 ,请计算上述 次操作全部结束后, 与 完全相同的概率。答案对 取模。
设该概率写成既约分数 ,你需要输出唯一的整数 ,满足 且 。可以证明,在本题的数据范围内, 一定存在。
输入格式
第一行包含一个整数 。
第二行包含 个整数 ,表示给定的排列。
输出格式
输出一行一个整数,表示所求概率对 取模的结果。
样例 1
样例输入
3
2 3 1
样例输出
406692144
解释
三次随机选择共有 种等可能的结果,其中 种得到排列 ,故所求概率为 。
样例 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 的约束条件。
数据范围
本题开启合理的子任务依赖。
| 子任务 | 特殊性质 | 分值 | |
|---|---|---|---|
| 无 | |||
| A | |||
| B | |||
| C | |||
| 无 |
将每个位置 向 连一条有向边,会得到一个由若干个互不相交的有向环组成的图。
特殊性质 A:上述图恰好由一个环组成。
特殊性质 B:上述图由至多两个环组成。
特殊性质 C:对于所有 ,均有 。
对于所有数据,,保证 是一个长度为 的排列。
