SRM338 div1 medium
最初のarray[a]=xとする
xがarray[a]にあるか、それ以外にあるかで確率を保持する。
一度swapするたびに
1:array[a]==xのとき
xが選ばれない確率は(nC2-n+1)/nC2
xが選ばれる確率は(n-1)/nC2
2:array[a]!=xのとき
xがarray[a]に移動する確率は1/nC2
xがarray[a]に移動しない確率は(nC2-1)/nC2
#include <cstdio> using namespace std; class RandomSwaps { public: double getProbability(int arrayLength, int swapCount, int a, int b) { double inA=1.0,inOther=0.0,n=arrayLength; double nC2=n*(n-1)/2; for(int i=0;i<swapCount;i++) { double a,o; a=inA*(nC2-(n-1))/nC2+inOther*1.0/nC2; o=inA*(n-1)/nC2+inOther*(nC2-1.0)/nC2; inA=a,inOther=o; } if(a==b) return inA; else return inOther/(n-1); } };