toj_2871.cpp

Tianjin University Online Judge 的80多道题目 .

#include<cstdio>
#include<cstring>
#define MAXNUM 30
#define NUMMOD 2007
int n , m , t;
int mp[ MAXNUM ][ MAXNUM ] , mpn[ MAXNUM ][ MAXNUM ];

void printMP( int amp[][ MAXNUM ] )
{
     int i , j;
     for( i = 0; i <= n; i++ ){
          for( j = 0; j <= n; j++ )
               printf( "%d " , int( amp[ i ][ j ] ) );
          printf( "\n" );
     }
     printf( "\n" );
}

void clac()
{
    int clcN ,  i , j , k;
    int tmp[ MAXNUM ][ MAXNUM ];
    memset( mpn , 0 , sizeof( mpn ) );
    for( i = 0; i <=n ; i++ )
        mpn[ i ][ i ]  = 1;
//        memcpy( mpn , mp , sizeof( mp ) );
    for( clcN = t   ; clcN > 0 ; ){
//         printf( " %d clcN mpn\n" );
        //        printMP( mpn  );
        if( clcN % 2 == 1 ){
            memset( tmp , 0 , sizeof( tmp ) );
            clcN--;
//            printf( "first tmp \n" );
//            printMP( tmp );
            for( i = 0;  i <= n; i++ ){
                for( j = 0; j <=n; j++ ){
                    for( k = 0; k <= n; k++ ){
                        tmp[ i ][ j ] += mpn[ i ][ k ] * mp[ k ][ j ];
                        tmp[i ][ j ] %= NUMMOD;
//                            printf( "%d  ??%d?? %d %d  " , mpn[ i ][ k ] * mp[ k ][ j ] , tmp[ i ][ j ] , mpn[ i ][ k ] , mp[ k ][j ] );
                    }
                }
            }
            memcpy( mpn , tmp , sizeof( tmp ) );
        }
//        memcpy( mpn , tmp , sizeof( tmp ) );
//        printf( "2 clac %d mpn \n" , clcN );
//      printMP( mpn );
//        printf( "?? tmp \n" );
//        printMP( tmp );
        clcN /= 2;
        memset( tmp , 0 , sizeof( tmp ) );
        for( i = 0; i <= n; i++ ){
            for( j = 0; j <= n; j++ ){
                for( k = 0;  k <= n; k++ ){
                    tmp[ i ][ j ] += mpn[ i ][ k ] * mpn[ k ][ j ];
                    tmp[ i ][ j ] %= NUMMOD;
                }
            }
        }
        memcpy( mpn , tmp , sizeof( tmp ) );
    }
//  printMP( mpn );
}



             
int main()
{
    freopen( "toj_2871.in" , "r" , stdin );
    freopen( "toj_2871.out" , "w" , stdout );
    int i , j , nodeA , nodeB , result;
    while( scanf( "%d%d"  , &n , &m ) != EOF && ( n || m ) ){
        memset( mp , 0 , sizeof( mp ) );
        for( i = 0; i < m; i++ ){
            scanf( "%d%d" , &nodeA , &nodeB );
            mp[ nodeA ][ nodeB ] = 1;
            mp[ nodeB ][ nodeA ] = 1;
        }
        scanf( "%d" , &t );
        for( i = 0; i <= n; i++ ){
            mp[ i ][ i ] = 1;
            mp[ i ][ 0 ] = 1;
        }
//        printf( "mp!!\n" );
//        printMP( mp );
        clac();
//        printMP( mpn );
        for( result = 0, i = 0; i <= n; i++ )
            result += mpn[ 1 ][ i ];
        printf( "%d\n" , result % NUMMOD  );
    }
    return 0;
}