题目大意
一个长度为 \(n\) 的数列，然后给你 \(q\) 个交换或不交换操作，你可以选择操作或者不操作，问所有情况下逆序对的总和。
答案需要对 \(10 ^ 9 + 7\) 取模。
（\(n\leq 3000\)，\(q\leq 3000\)）。
思路
这道题非常巧妙。
我们先考虑转化题意，求逆序对数量的期望。
记 \(dp_{i,j}\) 表示 \(a_i>a_j\) 的概率，初始值很好设，直接根据初始给出的排列情况进行赋值。
- 若 \(a_i>a_j\)，则 \(dp_{i,j}=1\)；
- 若 \(a_i < a_j\)，则 \(dp_{j,i}=1\)。
考虑如果我们交换 \(x\) 和 \(y\) 的位置，会产生什么影响。对于 \(\forall i,j \in \left[ 1,n \right]\)，其中 \(i,j\) 没有与 \(x\) 或 \(y\) 的情况，不会影响 \(dp_{i,j}\) 的值。
记 \(f_{i,j}\) 表示未更改前的 \(dp\) 数组，考虑有 \(x,y\) 的情况，显然有
\[dp_{i,x}=\dfrac{f_{i,x}+f_{i,y}}{2}
\]
\[dp_{i,y}=\dfrac{f_{i,x}+f_{i,y}}{2}
\]
\[dp_{x,i}=\dfrac{f_{x,i}+f_{y,i}}{2}
\]
\[dp_{y,i}=\dfrac{f_{x,i}+f_{y,i}}{2}
\]
这道题求的是逆序对的总和，所以答案应当是所有情况数与逆序对数量的期望的乘积。
所以最后答案为
\[2^m \times \sum^{n}_{i=1}\sum^{n}_{j=i+1}dp_{i,j}
\]
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int Mod = 1e9 + 7;
const int N = 3050;
int n,m;
int a[N];
long long Pow(long long a ,long long b) {
long long res = 1 ;
long long base = a;
while(b) {
if(b & 1)
res = res * base % Mod;
base = base * base % Mod;
b >>= 1;
}
return res;
}
long long Inv(int x) {
return Pow(x,Mod - 2) % Mod;
}
long long dp[N][N],ans = 0;
signed main() {
cin >> n >> m;
for(int i = 1;i <= n; i++)
cin >> a[i];
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,x,y;i <= m; i++) {
cin >> x >> y;
for(int i = 1;i <= n; i++) {
if(i == x || i == y)
continue;
dp[i][x] = dp[i][y] = (dp[i][x] + dp[i][y]) * Inv(2) % Mod;
dp[x][i] = dp[y][i] = (dp[x][i] + dp[y][i]) * Inv(2) % Mod;
}
dp[x][y] = dp[y][x] = (dp[x][y] + dp[y][x]) * Inv(2) % Mod;
}
for(int i = 1;i <= n; i++)
for(int j = i + 1;j <= n; j++)
ans = (ans + dp[i][j]) % Mod;
ans = 1ll * ans * Pow(2,m) % Mod;
cout << ans << "\n";
return 0;
}