toj_2871_zhaodongxue.cpp

Tianjin University Online Judge 的80多道题目 .

#include<stdio.h>
int a[22][22],aa[22][22],temp[22][22],temp1[22][22];
int N,M;
int juzhen(int t){
    int i,j,k;
    if(t==1)return;
    else juzhen(t/2);
    memset(temp,0,sizeof(temp));
    for(i=0;i<=N;i++)
        for(j=0;j<=N;j++)
            for(k=0;k<=N;k++){
                temp[i][j]+=a[i][k]*a[k][j];
                temp[i][j]%=2007;
            }
    if(t%2){
        memset(temp1,0,sizeof(temp1));
        for(i=0;i<=N;i++)
            for(j=0;j<=N;j++)
                for(k=0;k<=N;k++){
                    temp1[i][j]+=temp[i][k]*aa[k][j];
                    temp1[i][j]%=2007;
                }   
        for(i=0;i<=N;i++)
            for(j=0;j<=N;j++)a[i][j]=temp1[i][j];
    }
    else{for(i=0;i<=N;i++)
            for(j=0;j<=N;j++)a[i][j]=temp[i][j];
    }
}
int main(){
    int i,x,y,sum,tt;
    while(scanf("%d%d",&N,&M)){
        if(M==0&&N==0)break;
        memset(a,0,sizeof(a));
        memset(aa,0,sizeof(aa));
        while(M--){
            scanf("%d%d",&x,&y);
            a[x-1][y-1]=a[y-1][x-1]=aa[x-1][y-1]=aa[y-1][x-1]=1;
        }
        for(i=0;i<=N;i++)a[i][i]=aa[i][i]=1;
        for(i=0;i<=N;i++)a[i][N]=aa[i][N]=1;
        scanf("%d",&tt);
        juzhen(tt);
        for(sum=i=0;i<=N;i++){sum+=a[0][i];sum%=2007;}
        printf("%d\n",sum);
    }
    return 0;
}