Codeforces 258D Little Elephant and Broken Sorting

如果对每一对数考虑的话很不方便，因为每次交换的时候我们并不知道这个位置上放的是什么数。因此可以对每一对位置考虑。维护$f[i][j]$表示位置$i$比位置$j$大的概率。
实际上只要想到状态表示，后面的就很简单了。对于修改$(u,v)$，显然只有涉及到$u$或者$v$的值才可能改变，因此只需要修改$O(n)$个，大概就是$f[i][u]=f[i][v]=\frac{f[i][u]+f[i][v]}2$。总的复杂度$O(mn)$。

#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=1010;
int n,m,a[maxn];
double f[maxn][maxn];
int main()
{double ans=0;int u,v;scanf("%d%d",&n,&m);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]);while (m--){scanf("%d%d",&u,&v);for (int i=1;i<=n;i++)if (i!=u&&i!=v){f[i][u]=f[i][v]=(f[i][u]+f[i][v])/2;f[u][i]=f[v][i]=(f[u][i]+f[v][i])/2;}f[u][v]=f[v][u]=0.5;}for (int i=1;i<=n;i++)for (int j=i+1;j<=n;j++)ans+=f[i][j];printf("%.7f\n",ans);
}