[AGC030D] Inversion Sum 题解

标签：std Inversion right 题解 Sum typedef dfrac valueType left

题意

给定一个长度为 \(n\) 的排列 \(a\) 和 \(m\) 个形如 \(\left(x,y\right)\) 的操作，每次操作可以选择是否交换 \(a_x, a_y\)，求最终所有形成的排列的逆序对总数。

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

题解

考虑转化题意，考虑求出最终总的期望逆序对数，即 CF258D。

转化答案

\[\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}\]

所有操作处理完成后直接乘上所有可能的排列数即 \(2^m\) 即可得到本题答案。

每次操作 \(\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,Inversion,right,题解,Sum,typedef,dfrac,valueType,left
From： https://www.cnblogs.com/User-Unauthorized/p/solution-AGC030D.html