题意：给定n,k。k次操作，每次等概率将一个区间翻转，问最后逆序数对的期望。
思路：设dp[i][j]表示a[i]在a[j]前面的概率。每次枚举翻转的区间，更新dp[i][j]，复杂度为O(n^4×k)。详见代码：
/*********************************************************
file name: G.cpp
author : kereo
create time: 2015年02月09日 星期一 11时32分13秒
*********************************************************/
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<stack>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;
typedef long long ll;
const int sigma_size=26;
const int N=100+50;
const int MAXN=100000+50;
const int inf=0x3fffffff;
const double eps=1e-8;
const int mod=1000000000+7;
#define L(x) (x<<1)
#define R(x) (x<<1|1)
#define PII pair<int, int>
#define mk(x,y) make_pair((x),(y))
int n,k;
int a[N];
double dp[N][N],res[N][N];
int main(){
while(~scanf("%d%d",&n,&k)){
for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
memset(dp,0,sizeof(dp));
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
dp[i][j]=1;
while(k--){
memcpy(res,dp,sizeof(dp));
memset(dp,0,sizeof(dp));
for(int l=1;l<=n;l++)
for(int r=l;r<=n;r++){
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++){
int x=i,y=j;
if(l<=x && x<=r) x=l+r-x;
if(l<=y && y<=r) y=l+r-y;
if(x>y)
swap(x,y);
if(l<=x && y<=r) //在区间里面，则必然翻转，所以(1-res[i][j])
dp[x][y]+=(1-res[i][j])*2.0/(n+1)/n;
else
dp[x][y]+=res[i][j]*2.0/(n+1)/n;
}
}
}
double ans=0;
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(a[i]>a[j])
ans+=dp[i][j];
else
ans+=1.0-dp[i][j];
printf("%.10f\n",ans);
}
return 0;
}rockethon2015 G2题 Inversions problem 概率dp
原文：http://blog.csdn.net/u011645923/article/details/43675931