← 返回题目列表

Codeforces · 513/G3

G3. 反转问题

中文机器翻译题面 查看原题

给定 n 个数字 p1、p2、...、pn 的排列。我们执行以下类型的 k 个操作:均匀随机选择两个索引 l 和 r (l ≤ r) 并反转元素 pl, pl + 1, ..., pr 的顺序。您的任务是找到结果排列中反转次数的预期值。

输入

输入的第一行包含两个整数 n 和 k (1 ≤ n ≤ 100, 1 ≤ k ≤ 109)。下一行包含 n 个整数 p1, p2, ..., pn — 给定的排列。所有 pi 都不同,范围从 1 到 n。

该问题由三个子问题组成。子问题对输入有不同的约束。正确提交子问题将获得一些分数。子问题的描述如下。

- 在子问题 G1(3 点)中,约束 1 ≤ n ≤ 6、1 ≤ k ≤ 4 将成立。
- 在子问题 G2(5 分)中,约束 1 ≤ n ≤ 30、1 ≤ k ≤ 200 将成立。
- 在子问题 G3(16 点)中,约束 1 ≤ n ≤ 100、1 ≤ k ≤ 109 将成立。

输出

输出绝对或相对误差不超过 1e - 9 的答案。

示例

输入 #1

3 1
1 2 3

输出 #1

0.833333333333333

输入 #2

3 4
1 3 2

输出 #2

1.458333333333334

注意

考虑第一个样本测试。我们将随机选择一个排列区间 (1, 2, 3)(没有反转)并反转其元素的顺序。在概率为 $$\frac{1}{2}$$ 的情况下,区间将由单个元素组成,并且排列不会改变。我们将以 $${ \frac { 1 } { 6 } }$$ 的概率反转前两个元素的顺序并获得具有一次反转的排列 (2, 1, 3)。以相同的概率,我们可以选择由最后两个元素组成的区间,这将导致具有一次反转的排列 (1, 3, 2)。最后,随机选取的区间将以 $${ \frac { 1 } { 6 } }$$ 的概率包含所有元素,从而导致具有 3 次反转的排列 (3, 2, 1)。因此,预期的反转次数等于 $${ \frac { 1 } { 2 } } \cdot 0 + { \frac { 1 } { 6 } } \cdot 1 + { \frac { 1 } { 6 } } \cdot 1 + { \frac { 1 } { 6 } } \cdot 3 = { \frac { 5 } { 6 } }$$。