TopCoder SRM 338 Div1 Medium RandomSwaps

問題

n枚のカードがある。
これらのカードに対して、2枚のカードをランダムに選び、その位置を交換するという操作をswapCount回行う。
操作前にa番目にあったカードが操作後にb番目にある確率を求めよ。

制約条件

n≦1000
swapCount≦100000

方針

最初にa番目にあったカードが、i回の操作の後でb番目に来ている確率をp[i]とすると、
p[i+1]=(n-2)/n * p[i] + 2/(n*(n-1)) * (1-p[i])の漸化式が成り立つので、
これをswapCountまでまわせばよい。

swapCountが10億くらいまでだと思っていたので行列を使って計算した。

ソースコード

typedef vector<vd> mat;
mat operator*(mat a,mat b){
	mat res(2,vd(2));
	rep(i,2)rep(j,2)rep(k,2)res[i][j]+=a[i][k]*b[k][j];
	return res;
}
mat pow(mat m,int n){
	mat res(2,vd(2));
	res[0][0]=res[1][1]=1;
	for(;n;n/=2){
		if(n&1)res=res*m;
		m=m*m;
	}
	return res;
}

class RandomSwaps {
	public:
	double getProbability(int n, int c, int a, int b) 
	{
		if(n==2){
			return (a==b)^(c%2)?1:0;
		}
		mat m(2,vd(2));
		m[0][0]=(n-1.0)*(n-2)/(n*(n-1.0));
		m[0][1]=2.0/(n*(n-1.0));
		m[1][0]=2.0*(n-1)/(n*(n-1.0));
		m[1][1]=1-m[0][1];
		m=pow(m,c);
		mat t(2,vd(1));
		if(a==b)t[0][0]=1;
		else t[1][0]=1;
		m=m*t;
		return m[0][0];
	}
};