CF258D Little Elephant and Broken Sorting 题解

题目大意

有一个 \(1 \sim n\) 的排列，会进行 \(m\) 次操作，操作为交换两位置的数，每次操作都有 \(50\%\) 的概率进行，求 \(m\) 次操作之后的期望逆序对个数。（\(n, m \le 1000\)）

分析

感觉大体方向是比较好想的。看完数据范围，一眼期望 \(dp\)。那么就来考虑怎么设计 \(dp\)。

题解

第一反应想到计数，用 \(dp_{i, j}\) 来代表数对 \((i, j)\) 对最终答案作出的贡献。但是在写转移时发现有一点麻烦，于是浅改一下思路，用 \(dp_{i, j}\) 来代表位置 \(i\) 上的数比位置 \(j\) 上的数大的概率。

我们很容易得到，最终答案就是 \(\displaystyle \sum_{i = 1}^{n} \sum_{j = i + 1}^{n} dp_{i, j}\)。

\(dp\) 的初始值比较好想，就是 \(O(n^2)\) 跑一遍，对于每一个 \(i\) 位置上的数大于 \(j\) 位置上的数的情况，把 \(dp_{i, j}\) 赋成 \(1\) 即可。接下来我们考虑操作一次会使 \(dp\) 怎样变化。假设我们这一次操作所交换的两个位置是 \(x\) 和 \(y\)，\(x\) 位置上的数为 \(a_x\)，\(y\) 位置上的数为 \(a_y\)。

最好想的就是 \(dp_{x, y}\) 和 \(dp_{y, x}\) 如何变化。首先我们想到，因为这是一个排列，所以每一个位置上的数不相同，所以再交换 \(x\) 和 \(y\) 以后，\(dp_{x, y}\) 和 \(dp_{y, x}\) 都会被直接赋值成 \(0.5\)。

而对于其他的位置上的数，比如我们再设一个位置 \(t(1 \le t \le n \land t \neq x \land t \neq y)\)（\(\land\) 是“且”的意思，\(\lor\) 是“或”的意思），其位置上的数为 \(a_t\)，那么一定有：

\[\begin{aligned} dp_{x, t} &= 1 - dp_{t, x}\\ dp_{x, t} &= 1 - dp_{t, x}\\ dp_{t, x} = dp_{t, y} &= \frac{dp_{t, x} + dp_{t, y}}{2}\\ dp_{x, t} = dp_{y, t} &= \frac{dp_{x, t} + dp_{y, t}}{2} \end{aligned} \]

前两个式子显然成立（但是好像这个题没用上），我们考虑怎么去证明后两个式子。其实也很好证，因为如果两者换位成功，则 \(dp_{t, x} = dp_{t, y}\)，否则不变。而我们又知道，成功的几率为 \(0.5\)，那么 \(\displaystyle dp_{t, x} = \frac{dp_{t, x} + dp_{t, y}}{2}\) 显然成立。其他的同理。

既然有了这些结论，那么我们就可以对于每一次操作，枚举一遍 \(t\)。再算上给 \(dp\) 赋初值的时间复杂度，那么总的时间复杂度就是 \(O(n^2 + mn)\)。

代码

//https://www.luogu.com.cn/problem/CF258D Little Elephant and Broken Sorting
#include <bits/stdc++.h>
#define M 1005

using namespace std;

inline int read() {
    int x = 0, s = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-')
            s = -s;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar();
    }
    return x * s;
}

void write(int x) {
    if(x < 0)  {
        x = ~(x - 1);
        putchar('-');
    }
    if(x > 9)
        write(x / 10);
    putchar(x % 10 + 48);
}

int n, m, a[M];
long double dp[M][M], ans;

signed main() {
    n = read();
    m = read();
    for(int i = 1; i <= n; ++ i)
        a[i] = read();
    for(int i = 1; i <= n; ++ i)
        for(int j = 1; j <= n; ++ j)
            if(a[i] > a[j])
                dp[i][j] = 1;
    for(int i = 1; i <= m; ++ i) {
        int x = read(), y = read();
        if(x == y)
            continue;
        for(int j = 1; j <= n; ++ j) {
            if(j != x && j != y) {
                dp[y][j] = dp[x][j] = dp[x][j] / 2 + dp[y][j] / 2;
                dp[j][y] = dp[j][x] = dp[j][x] / 2 + dp[j][y] / 2;
            }
        }
        dp[x][y] = 0.5;
        dp[y][x] = 0.5;
    }
    for(int i = 1; i <= n; ++ i)
        for(int j = i + 1; j <= n; ++ j)
            ans += dp[i][j];
    printf("%Lf", ans);
}