题意：长度为n的排列，m次交换xi, yi，每个交换x，y有50%的概率不发生，问逆序数的期望 。n, m <= 1000
思路：我们只用维护大小关系，dp[i][j]表示位置i的数比位置j的数大的概率。
那么每次交换x和y。 假设x<y，那么区间就有三种: [1,x-1]，[x+1,y-1]， [y+1,N]， 不难证明这三个区间和xy处的逆序对关系变为二者和的一半。
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
double dp[maxn][maxn],ans; int a[maxn];
int main()
{
int N,M,x,y; scanf("%d%d",&N,&M);
rep(i,,N) scanf("%d",&a[i]);
rep(i,,N)
rep(j,,N)
dp[i][j]=a[i]>a[j];
rep(i,,M){
scanf("%d%d",&x,&y);
rep(j,,N){
if(j==x||j==y) continue;
dp[j][x]=dp[j][y]=(dp[j][x]+dp[j][y])/;
dp[x][j]=dp[y][j]=(dp[x][j]+dp[y][j])/;
}
dp[x][y]=dp[y][x]=0.5;
}
rep(i,,N) rep(j,i+,N) ans+=dp[i][j];
printf("%.6lf\n",ans);
return ;
}