开始 2022-07-20 11:50:00

强基3

结束 2022-07-20 12:50:00
Contest is over.
当前 2024-12-22 15:08:25

C. 敏捷排列

描述

现在有一个 1 ∼ n 的排列 {ai}。小谢可以对这个数组执行以下两种操作: • Swap,交换排列中任意两个数,花费是 a • Shuffle,将排列随机打乱,也就是说,会以等概率变为 1 ∼ n 的任一种排列,花费是 b 小谢的目标是将 {ai} 变为 1 ∼ n 的正序排列,即 ai = i,他想知道,在最优的策略下,花费的期望是多 少。

输入

第一行三个整数 n, a, b 第二行 n 个整数,表示数组 {ai} 的初始状态

输出

一个数字,表示花费的期望。你的答案会被认为是正确的当且仅当它与标准答案的误差小于 10−8。

样例

输入

2 5 5
1 2

输出

0.00000000000000000000

Submit

登录

注册
时间限制 1 秒
内存限制 256 MB
提交