7409. 逆序对概率 (Inversion Probability)
时间限制：1000 MS 内存限制：512 MB
题目描述
# 逆序对概率 (Inversion Probability) 时间限制：$1.00\text{ s}$ 空间限制：$512\text{ MB}$ ## 题目描述 有一个包含 $n$ 个整数的数组 $x_1,x_2,\dots,x_n$，每个元素 $x_i$ 都是在 $1$ 到 $r_i$ 之间独立、随机等概率选择的一个整数。一个逆序对定义为一对满足 $a<b$ 且 $x_a>x_b$ 的下标 $(a,b)$。 请问该数组中逆序对数量的数学期望是多少？ ## 输入格式 第一行包含一个整数 $n$：数组的大小。 第二行包含 $n$ 个整数 $r_1,r_2,\dots,r_n$：代表数组各位置可能取得的最大值。 ## 输出格式 输出逆序对数量的数学期望，四舍五入并保留六位小数（若刚好处于中间值则向最接近的偶数舍入）。 ## 输入输出样例 ### 输入 #1 ```text 3 5 2 7 ``` ### 输出 #1 ```text 1.057143 ``` ## 说明/提示 ### 数据规模与约定 - $1 \le n \le 100$ - $1 \le r_i \le 100$ ---