[TIOJ] 1136. 3.熱鍋上的螞蟻

題目連結:http://tioj.infor.org/problems/1136

---

因為我們知道若把圖用鄰接矩陣存下來，他的t次方就是走t步後有幾種走法，所以就可以看下面的做法做了。
本題要求的其實就是從所有a($0 \leq a \leq n$)開始走到x的機率和最後再除以n，但是顯然直接乘再算機率會overflow(除非你寫大數)，所以有個比較方便的技巧就是一開始就算機率，之後做矩陣乘法的時候就不會因此而overflow了，大概這樣就可以AC了吧

#include <bits/stdc++.h>
using namespace std;

typedef double lf;
typedef long long lld;

#define N 100

auto m1 = new lf[N+10][N+10];
auto m2 = new lf[N+10][N+10];
auto m3 = new lf[N+10][N+10];
lld mm[N+10][N+10];

inline void mTimes(lf[][N+10],lf[][N+10],lf[][N+10]);

int n,t;
int main(){
	scanf("%d%d",&n,&t);
	while(n+t!=0){
		for(int i=0;i<n;i++)for(int j=0;j<n;j++)m1[i][j]=m2[i][j]=m3[i][j]=mm[i][j]=0;
		int x;
		scanf("%d",&x);
		while(x--){
			int s,t;
			scanf("%d%d",&s,&t);
			s--,t--;
			mm[s][t]=1;
			mm[t][s]=1;
		}
		for(int i=0;i<n;i++){
			lld sum=0;
			for(int j=0;j<n;j++) sum+=mm[i][j];
			if(sum==0)
				for(int j=0;j<n;j++) m2[i][j] = 0;
			else
				for(int j=0;j<n;j++) m2[i][j] = (lf)mm[i][j]/(lf)sum;
		}
		for(int i=0;i<n;i++)m1[i][i]=1;
		while(t){
			if(t&1){
				mTimes(m1,m2,m3);
				swap(m1,m3);
			}
			mTimes(m2,m2,m3);
			swap(m2,m3);
			t>>=1;
		}
		int target;
		scanf("%d",&target);
		target--;
		double ans=0;
		for(int i=0;i<n;i++){
			ans += m1[i][target];
		}
		printf("%.4lf\n",ans/(lf)n);
		scanf("%d%d",&n,&t);
	}
	return 0;
}

inline void mTimes(lf a[][N+10],lf b[][N+10],lf c[][N+10]){
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			c[i][j]=0;
			for(int k=0;k<n;k++) c[i][j] += a[i][k]*b[k][j];
		}
	}
}