Inversion Probability

题目描述

数组包含 n 个整数 $x_1,x_2,\dots,x_n$，每个整数都是在 1 到 $r_i$ 之间随机选择的。一个逆序对是指满足 $a<b$ 且 $x_a>x_b$ 的一对索引 $(a,b)$。 数组中逆序对的期望值是多少？

输入格式

第一行输入包含一个整数 n：数组的大小。 第二行包含 n 个整数 $r_1,r_2,\dots,r_n$：每个数组位置可能取值的范围。

输出格式

输出逆序对的期望值，四舍六入（保留 6 位小数，采用舍入到最近的偶数规则）。

3
5 2 7

1.057143

提示

$1 \le n \le 100$ $1 \le r_i \le 100$

标签: CSES1728|数学

来源

CSES1728|数学