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);
		}
};