Codeforces Round #157 (Div. 1) D. Little Elephant and Broken Sorting

1~nを並び替えた数列があって、a番目とb番目を入れ替えるクエリがm個来るが、それぞれのクエリは1/2の確率でしか実行されない
この時クエリをm個処理した後の反転数の期待値を求めよ

p[i][j] : i番目 < j番目という配列を持って、クエリに対して順番に確率を計算していけば、
最後に足し合わせることで期待値が求まる。
Div1Dにしては軽実装

#include <cstdio>

using namespace std;

#define rep(i, m) for(int i = 0; i < (int)m; ++i)

int n, m;
int a[1010];
double ret;
double p[1010][1010];

int main(){
    scanf("%d %d", &n, &m);
    rep(i, n) scanf("%d", &a[i]);
    rep(i, n) rep(j, n) if(i != j) p[i][j] = (a[i] > a[j] ? 1.0 : 0.0);
    while(m--){
	int a, b; scanf("%d %d", &a, &b); --a; --b;
	p[a][b] = p[b][a] = 0.5;
	rep(i, n) if(i != a && i != b){
	    p[i][a] = p[i][b] = (p[i][a] + p[i][b]) / 2.0;
	    p[a][i] = p[b][i] = 1.0 - p[i][a];
	}
    }
    rep(i, n) rep(j, i) ret += p[j][i];
    printf("%.8lf\n", ret);
    return 0;
}