CF258D Little Elephant and Broken Sorting
题意
题意翻译
有一个\(1\sim n\)的排列，会进行\(m\)次操作，操作为交换\(a,b\)。每次操作都有\(50\%\)的概率进行。
求进行\(m\)次操作以后的期望逆序对个数。
\(n,m\le 1000\)
输入输出格式
输入格式：
The first line contains two integers \(n\) and \(m\) \((1\leq n,m\leq 1000,n>1)\) — the permutation size and the number of moves. The second line contains \(n\) distinct integers, not exceeding \(n\) — the initial permutation. Next \(m\) lines each contain two integers: the \(i\)-th line contains integers \(a_{i}\) and \(b_{i}\) \((1\leq a_{i},b_{i}\leq n,a_{i}\neq b_{i})\) — the positions of elements that were changed during the \(i\)-th move.
输出格式：
In the only line print a single real number — the answer to the problem. The answer will be considered correct if its relative or absolute error does not exceed \(10^{-6}\).
输入输出样例
输入样例#1：
2 11 21 2
输出样例#1：
0.500000000
输入样例#2：
4 31 3 2 41 22 31 4
输出样例#2：
3.000000000
思路
这道题真的水。 --Mercury
完全想不到的状态设计，感谢\(Mercury\)巨佬的指点。
定义\(f(i,j)\)为位置\(i\)上的数比位置\(j\)上的数大的概率。假设每次交换都是\(100\%\)成功的，不妨设这次交换的数的下标为\(a,b\)，那么对于任意的\(f(i,a),f(i,b)\)就要被交换，\(f(a,i),f(b,i)\)也要被交换。可是当前交换的概率是\(50\%\)的，所以\(f(i,a),f(i,b)\)之间的差值要被分别减少\(50\%\)，也就相当于\(f(i,a)=f(i,b)=(f(i,a)+f(i,b))\div 2\)。同理，\(f(a,i)=f(b,i)=(f(a,i)+f(b,i))\div 2\)。最后的逆序对期望，也就是\(\Sigma [i<j]f(i,j)\times 1\)，也就是\(\Sigma [i<j]f(i,j)\)。
还要再胡扯两句。其实只要想出了\(f(i,j)\)这个东西，什么都简单了，可是又会有几个人能够想到这种方法呢？完全没有类似的情况作为参考，掌握了这道题却又能给类似的题提供经验（毕竟也没有类似的题）。下一次见到了这种思维量大的题，还是不太能想得出。思维的活跃在\(OI\)中还是有很大的作用的啊！
AC代码
#include<bits/stdc++.h>#define RG registerusing namespace std;int n,m,a[1005];double ans,f[1005][1005];int read(){RG int re=0;RG char ch=getchar();while(!isdigit(ch)) ch=getchar();while(isdigit(ch)) re=(re<<3)+(re<<1)+ch-'0',ch=getchar();return re;}int main(){n=read(),m=read();for(RG int i=1;i<=n;i++) a[i]=read();for(RG int i=1;i<=n;i++)for(RG int j=i+1;j<=n;j++)if(a[i]>a[j]) f[i][j]=1.0;else f[j][i]=1.0;while(m--){RG int x=read(),y=read();if(x==y) continue;for(RG int i=1;i<=n;i++){if(i==x||i==y) continue;f[i][x]=f[i][y]=(f[i][x]+f[i][y])/2;f[x][i]=f[y][i]=(f[x][i]+f[y][i])/2;}f[x][y]=f[y][x]=0.5;}for(RG int i=1;i<=n;i++)for(RG int j=i+1;j<=n;j++)ans+=f[i][j];printf("%.8f",ans);return 0;}
