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

76695    nolonger    3136K    1591MS    G++     1.19K     2010-05-12 23:24:38                                .


蚯蚓：「看到範圍10^9不是很明顯嗎？」

然後就瞬間領悟了。


第二題co 矩陣相乘

是說最後模考還是寫爆了orz



//**************************************

#include<stdio.h>
bool con[110][110];
int n, t, a, b, cnt[110], c, pre, x;
double tmp[110][110];
struct Matrix{
    double a[110][110];
    void operator*= (Matrix b){
        for(int i=1; i<=t; i++)
            for(int j=1; j<=t; j++)
                tmp[i][j]= .0;
        for(int i=1; i<=t; i++)
            for(int j=1; j<=t; j++)
                for(int k=1; k<=t; k++)
                    tmp[i][j]+= a[i][k]*b.a[k][j];
        for(int i=1; i<=t; i++)
            for(int j=1; j<=t; j++)
                a[i][j]= tmp[i][j];
    }
}n2[40], ans;

int main(){
    while(~scanf("%d%d", &t, &n)){
        if(!n&&!t)break;
        scanf("%d", &c);
        //Init
        for(int i=1; i<=t; i++){
            cnt[i]= 0;
            for(int j=1; j<=t; j++){
                con[i][j]= 0;
                ans.a[i][j]= .0;
            }
            ans.a[1][i]= 1./t;
        }
        //Input
        while(c--){
            scanf("%d%d", &a, &b);
            ++cnt[a]; ++cnt[b];
            con[a][b]= con[b][a]= 1;
        }
        //Construct
        for(int i=1; i<=t; i++)
            for(int j=1; j<=t; j++)
                n2[0].a[i][j]= (cnt[i]&& con[i][j])? (1./cnt[i]): .0;
        //Matrix
        for(pre=1; (1<<pre)<=n; pre++){
            n2[pre]= n2[pre-1];
            n2[pre]*=n2[pre-1];
        }
        //Compute
        for(; pre>=0; pre--){
            if((1<<pre)<=n){
                n-=(1<<pre);
                ans*= n2[pre];
            }
        }
        scanf("%d", &x);
        printf("%.4lf\n", ans.a[1][x]);
    }
}