[AGC030D] Inversion Sum

题解

\(f_{ij}\) 表示 \(A_i < A_j\) 的概率。

每次修改 \(\mathcal O(n)\) 更新一下就行。

最后求出逆序对个数的期望,乘以 \(2^q\) 就是答案。

代码

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
38
39
40
41
42
43
44
45
46
47
48
49
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 3010;
const int mod = 1e9+7;

int A[maxn], f[maxn][maxn];

int n, q;

int main() {
scanf("%d%d", &n, &q);
for (int i = 1; i <= n; i++) scanf("%d", &A[i]);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
f[i][j] = (A[i] < A[j]);
}
}
for (int i = 1; i <= q; i++) {
int x, y; scanf("%d%d", &x, &y);
int inv = (mod + 1) / 2;
for (int j = 1; j <= n; j++) {
if (j != x && j != y) {
int s = 1LL * (f[j][x] + f[j][y]) * inv % mod;
f[j][x] = f[j][y] = s;
}
}
for (int j = 1; j <= n; j++) {
if (j != x && j != y) {
int s = 1LL * (f[x][j] + f[y][j]) * inv % mod;
f[x][j] = f[y][j] = s;
}
}
int s = 1LL * (f[x][y] + f[y][x]) * inv % mod;
f[x][y] = f[y][x] = s;
}
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j < i; j++) {
ans = (ans + f[i][j]) % mod;
}
}
for (int i = 1; i <= q; i++) ans = 1LL * ans * 2 % mod;
printf("%d\n", ans);
return 0;
}