题意
给定一个长度为 \(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;
}