[Aug6] Random

这道期望题真是鬼畜…

题意

现在你有一个n个数的排列,有两种操作:

 1. 交换相邻两个元素;
 2. 将整个排列随机打乱,随机打乱后出现任意一种排列的概率都是相等的。

现在你最多对这个排列执行 k 次操作,问在最优(使最终排列逆序对数量最少)策略下,最终的排列的逆序对数量的数学期望是多少。

思路

令 $ f[i][j][k] $为长度为 $ i $ ,逆序对个数为 $ j $ ,剩余次数为 $ k $ 的最终排列逆序对期望。

$ g[i][j] $表示长度为 $ i $ 的随机排列,剩余次数为 $ k $ 的最终排列逆序对期望。

有 $ g[i][j] = \frac{1}{i!} \sum_{P(i)}{f[i][Inv(P(i))][j]}​$,

枚举逆序对个数,设 $ p[i][j] $ 为长度为 $ i $ 的随机排列逆序对个数为 $ k $ 的概率,有 $ g[i][j] = \sum_{k}{f[i][k][j] \times p[i][k]} $。

求值时,根据 $ f[i][k][j] $ 的值不同分开求值。

  • $ k \leq j $ 时可以直接将序列变得有序,值为 $ 0 $ 。
  • $ j \lt k \leq \lfloor \; j +g[i][j - 1] \; \rfloor $时,逆序对个数不能为 $ 0 $,但是交换一次的结果大于随机一次结果的期望。值为 $ k - j $。
  • 其他情况下随机一次,值为 $ g[i][j - 1]$ 。

求值前可以先预处理 $ p[i][j] $ 和 $ p[i][j] \times j $ 的值。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
const int N = 101,N2 = 4951;
int n,k,a[N];
double g[N][N2],p[N][N2],P[N][N2],Pi[N][N2];
int main()
{
p[1][0] = 1.0;
for(int i = 1;i < N;i++) for(int j = 0,ii = (i - 1) * i / 2;j <= ii;j++) for(int k = 0;k <= i;k++) p[i + 1][j + k] += p[i][j] / (i + 1);
for(int i = 1;i < N;i++) for(int j = 0,ii = (i - 1) * i / 2;j <= ii;j++) P[i][j] = P[i][j - 1] + p[i][j],Pi[i][j] = Pi[i][j - 1] + p[i][j] * j;
for(int i = 1;i < N;i++)
{
int ii = (i - 1) * i / 2;
g[i][0] = Pi[i][ii];
for(int j = 1;j <= ii;j++)
{
int s = std::min(j + (int)floor(g[i][j - 1]),ii);
g[i][j] += g[i][j - 1] * (P[i][ii] - P[i][s]);
g[i][j] += Pi[i][s] - Pi[i][j];
g[i][j] -= j * (P[i][s] - P[i][j]);
}
}
int T;scanf("%d",&T);while(T--)
{
scanf("%d%d",&n,&k);
int tot = 0;
for(int i = 1;i <= n;i++)
{
scanf("%d",&a[i]);
for(int j = 1;j < i;j++) tot += (a[j] > a[i]);
}
printf("%f\n",std::min(1.0 * std::max(0,tot - k),g[n][std::min(k - 1,(n - 1) * n / 2)]));
}
return 0;
}