CF258D Little Elephant and Broken Sorting

$\color{deeppink}link$

$n$ 阶排列，$m$ 次操作，每次操作有 $0.5$ 的概率交换 $x,y$，最后求期望的逆序对个数。

由于和的期望等于期望的和，故可以将总的逆序对个数化为每个对为逆序对的期望之和。

令 $f_{i,j}$ 为 $P(a_i>a_j)$。当交换 $x,y$ 时，考虑对 $t$ 的贡献。

显然 ，$f_{t,i}=\dfrac{f_{t,i}+f_{t,j}}{2}$，$f_{t,j}$ 一样的。

对于 $x,y$，有 $f_{x,t}=f_{y,t}=1-f_{t,x},f_{x,y}=f_{y,x}=\dfrac{1}{2}$。还要注意 $f_{i,i}$ 永远为 $0$。

每次操作枚举一遍即可，时间是 $O(nm)$。

#include<bits/stdc++.h>
#define db double
using namespace std;
const int N=2e3+50;

int n,m,a[N],x,y;
db f[N][N],ans;

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++)
	f[i][j]=(a[i]>a[j]);
	while(m--)
	{
		cin>>x>>y;
		for(int i=1;i<=n;i++)
		{
			f[i][x]=f[i][y]=(f[i][y]+f[i][x])/2;
			f[x][i]=f[y][i]=1-f[i][x];
		}
		f[x][x]=f[y][y]=0;
		f[x][y]=f[y][x]=0.5;
	}
	for(int i=1;i<=n;i++)
	for(int j=i+1;j<=n;j++)
	ans+=f[i][j];
	cout<<fixed<<setprecision(14)<<ans;
}