CF258D Little Elephant and Broken Sorting 题解

标签：std CF258D Sorting 题解 valueType typedef right dfrac left

题意

给定一个长度为 \(n\) 的排列 \(a\) 和 \(m\) 个形如 \(\left(x,y\right)\) 的操作，每次操作有 \(50\%\) 的概率交换 \(a_x, a_y\)，求最终排列的期望逆序对数。

（\(1 \le n,m \le 5000\)）。

题解

首先转化答案

\[\text{Ans} = \sum\limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} \operatorname{P}\left(a_i > a_j\right) \]

考虑设 \(f_{i, j} = \sum\limits_{i = 1}^{n} \sum\limits_{j = i + 1}^{n} \operatorname{P}\left(a_i > a_j\right)\)。初始值很显然

\[f_{i, j} = \left[a_i > a_j\right] \]

考虑交换操作 \(\left(x, y\right)\) 对该数组值的影响，设 \(g\) 为原数组，对于 \(\forall t \neq x \land t \neq y\)，有

\[\begin{aligned} f_{t, x} &= \dfrac{1}{2} g_{t, x} + \dfrac{1}{2} g_{t, y} \\ f_{t, y} &= \dfrac{1}{2} g_{t, x} + \dfrac{1}{2} g_{t, y} \\ f_{x, t} &= \dfrac{1}{2} g_{x, t} + \dfrac{1}{2} g_{y, t} \\ f_{y, t} &= \dfrac{1}{2} g_{x, t} + \dfrac{1}{2} g_{y, t} \\ \end{aligned}\]

因为原数组为排列，即元素互不相同，那么对于 \(x, y\)，有

\[\begin{aligned} f_{x, y} &= 0.5 \\ f_{y, x} &= 0.5 \\ \end{aligned}\]

每次操作 \(\mathcal{O}(n)\) 维护即可，总复杂度 \(\mathcal{O}(n^2 + nm)\)，可以通过本题。

Code

#include <bits/stdc++.h>

typedef int valueType;
typedef std::vector<valueType> ValueVector;
typedef double realType;
typedef std::vector<realType> realVector;
typedef std::vector<realVector> realMatrix;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType N, M;

    std::cin >> N >> M;

    ValueVector source(N + 1);
    realMatrix F(N + 1, realVector(N + 1, 0));

    for (valueType i = 1; i <= N; ++i)
        std::cin >> source[i];

    for (valueType i = 1; i <= N; ++i) {
        for (valueType j = i + 1; j <= N; ++j) {
            if (source[i] > source[j]) {
                F[i][j] = 1.0;
            } else {
                F[j][i] = 1.0;
            }
        }
    }

    for (valueType t = 0; t < M; ++t) {
        valueType a, b;

        std::cin >> a >> b;

        for (valueType i = 1; i <= N; ++i) {
            if (i == a || i == b)
                continue;

            F[i][a] = F[i][b] = (F[i][a] + F[i][b]) / 2;
            F[a][i] = F[b][i] = (F[a][i] + F[b][i]) / 2;
        }

        F[a][b] = F[b][a] = 0.5;
    }

    realType ans = 0;

    for (valueType i = 1; i <= N; ++i) {
        for (valueType j = i + 1; j <= N; ++j) {
            ans += F[i][j];
        }
    }

    std::cout << std::fixed << std::setprecision(10) << ans << std::endl;

    return 0;
}

标签：std,CF258D,Sorting,题解,valueType,typedef,right,dfrac,left
From： https://www.cnblogs.com/User-Unauthorized/p/solution-CF258D.html