题意:
有一个1~n的排列,依次进行m次操作,第i次操作表示为((x _i,y_i)),交换以这两个值为下标的元素,每次操作有一半的概率成功,你需要求出最后序列的逆序对的期望个数.
分析:
因为逆序对是(x,y)的形式,那么考虑每一对(i,j)对答案的贡献.
(f_{i,j})表示(a_i>a_j)的概率,我们发现每一个操作只影响(O(n))个f值,于是可以处理出每一个f的初始值,每次更新受影响的值即可。
时间复杂度 (O(NM)), 空间复杂度 (O(N^2)).
int n,m,a[1005];
double ans,f[1005][1005];
int main(){
n=read();m=read();
//对于长度为n的序列,有m次操作
for(int i=1;i<=n;i++)
a[i]=read();
//读入序列
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
f[i][j]=a[i]>a[j];
//预处理出f数组的初始值
for(int i=1;i<=m;i++){
int x=read(),y=read();
for(int j=1;j<=n;j++){
f[x][j]=f[y][j]=(double)0.5*(f[x][j]+f[y][j]);
f[j][x]=f[j][y]=(double)0.5*(f[j][x]+f[j][y]);
}
//是否交换x,y的概率为0.5,
//则a[x]>a[j]和a[y]>a[j]的概率取决于它们的和.
//2式写成f[j][x]=f[j][y]=1-f[x][j]应该也可以.
f[x][y]=f[y][x]=0.5;
//是否交换x,y的概率为0.5,
//所以a[x]>a[y]和a[y]>a[x]的概率都是0.5.
}
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
ans+=f[i][j];
//累加所有逆序对的概率
printf("%.8lf",ans);
//答案保留到小数点后8位
return 0;
}