Inversions problem

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

给定长度为 $n$ 的排列 $p_1,p_2,\ldots,p_n$。进行 $k$ 次独立随机操作：每次从所有满足 $1\le l\le r\le n$ 的区间中等概率选择一个，并反转 $p_l,p_{l+1},\ldots,p_r$ 的顺序。

求操作结束后排列逆序对数量的期望值。

输入格式

第一行两个整数 $n,k$。第二行 $n$ 个整数 $p_1,p_2,\ldots,p_n$，构成 $1$ 到 $n$ 的排列。

输出格式

输出期望逆序对数。若答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。

样例输入 1

3 1
1 2 3

样例输出 1

0.833333333333333

样例输入 2

3 4
1 3 2

样例输出 2

1.458333333333334

数据范围

对于所有数据，$1\le n\le100$，$1\le k\le10^9$，且 $p$ 为 $1$ 到 $n$ 的排列。

每个测试点独立计分。

说明

样例 1 中共有六个可选区间。反转两个长度为 $2$ 的区间分别产生一个逆序对，反转整个排列产生三个逆序对，其余区间不改变排列，因此期望为 $5/6$。