Codeforces 113 D. Museum

問題

n個の部屋がm本の通路により結ばれている。
二人が次のように移動する。

• 最初それぞれa,bの部屋にいる。
• 部屋ごとに定められている確率p[i]で、その場にとどまり、1-p[i]の確率で、通路を等確率で一つ選び、隣の部屋に移動する
• 二人の移動先が同じ部屋だったらそこで移動が終了する。

二人がそれぞれの部屋で出会う確率を求めよ。

制約条件

n≦22
0.01≦p[i]≦0.99

方針

遷移行列を作って、収束するまで累乗する。
ただし定数倍が結構厳しいので、2つ工夫が必要。

一つは、二人の居る部屋(a,b)についてa≦bとして、行列の成分を半分にすること。
もう一つは、行列の乗算の途中で非正規化数（1e-100くらいの小さい数）が出てきたら、
計算がものすごく遅くなる（30倍くらいかかるらしい）ので、0に置き換えること。

これらの工夫により制限時間内に実行が終わるようになる。

ソースコード

int n,m,a,b;
vector<vector<int> > e;
double p[22],A[256][256],B[256][256];

void run()
{
	cin>>n>>m>>a>>b;
	a--; b--;
	if(a>b)swap(a,b);
	e.clear(); e.resize(n);
	rep(i,m){
		int s,t; cin>>s>>t;
		e[--s].pb(--t);
		e[t].pb(s);
	}
	rep(i,n)cin>>p[i];
	
	double prob[22][22]={};
	rep(i,n)rep(j,n){
		if(i==j)prob[i][i]=p[i];
		else if(find(all(e[i]),j)!=e[i].end())prob[i][j]=(1-p[i])/e[i].size();
	}
	for(int i=0,c=0;i<n;i++)for(int j=i;j<n;j++,c++){
		if(i==j)A[c][c]=1;
		else{
			for(int k=0,d=0;k<n;k++)for(int l=k;l<n;l++,d++){
				if(k==l)A[d][c]=prob[i][k]*prob[j][l];
				else A[d][c]=prob[i][k]*prob[j][l]+prob[i][l]*prob[j][k];
			}
		}
	}
	int N=n*(n+1)/2;
	
	rep(it,17){
		rep(i,N)rep(j,N)rep(k,N)B[i][j]+=A[i][k]*A[k][j];
		rep(j,N){
			double s=0;
			rep(i,N){
				A[i][j]=B[i][j];
				B[i][j]=0;
				if(A[i][j]<1e-20)A[i][j]=0;
			}
		}
	}
	for(int i=0,c=0;i<n;i++)for(int j=i;j<n;j++,c++)
	for(int k=0,d=0;k<n;k++)for(int l=k;l<n;l++,d++)
	if(i==j&&k==a&&l==b)printf("%.9f%c",A[c][d],' ');
	puts("");
}