Description
加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且
放在了加里敦星球的1号城市上。这个可乐机器人有三种行为：停在原地，去下一个相邻的
城市，自爆。它每一秒都会随机触发一种行为。现在给出加里敦星球城市图，在第0秒时可
乐机器人在1号城市，问经过了t秒，可乐机器人的行为方案数是多少？
Input
第一行输入两个正整数N,M表示城市个数，M表示道路个数。(1≤N≤30,0≤M≤100)
接下来M行输入u,v表示u,v之间有一条道路。
(1≤u,v≤n)保证两座城市之间只有一条路相连。
最后输入时间t。1<t≤10^6
Output
输出可乐机器人的行为方案数，答案可能很大，请输出对2017取模后的结果。
Sample Input
3 2
1 2
2 3
2
1 2
2 3
2
Sample Output
8
Solution
第一次做到这种以图的形式的递推用矩阵乘法优化的
貌似是套路题但是我不会啊T_T
于是观摩了一波题解弄懂了这种类型的题目
一般是这种T很大N很小的题目就可以矩阵乘法优化
要求走T次就是对邻接矩阵自乘T次...
/**************************************************************
Problem: 4887
User: henryy
Language: C++
Result: Accepted
Time:80 ms
Memory:1456 kb
****************************************************************/
#include <bits/stdc++.h>
using namespace std ;
#define mod 2017
int n , m ;
struct matrix {
int m[ ][ ] ;
matrix() {
memset( m , , sizeof( m ) ) ;
}
int *operator[] ( int a ) { return m[ a ] ; }
matrix operator * ( matrix &x ) {
matrix ans ;
memset( ans.m , , sizeof( ans.m ) ) ;
for( int i = ; i <= n ; i ++ ) {
for( int j = ; j <= n ; j ++ ) {
for( int k = ; k <= n ; k ++ ) {
ans[ i ][ j ] = (ans[ i ][ j ] + m[ i ][ k ] * x[ k ][ j ] ) % mod ;
}
}
}
return ans ;
}
} a ;
matrix power( matrix x , int b ) {
matrix ans , base = x ;
for( int i = ; i <= n ; i ++ ) ans[ i ][ i ] = ;
while( b ) {
if( b & ) ans = ans * base ;
base = base * base ;
b >>= ;
}
return ans ;
}
int main() {
scanf( "%d%d" , &n , &m ) ;
for( int i = ; i <= m ; i ++ ) {
int x , y ;
scanf( "%d%d" , &x , &y ) ;
a[ x ][ y ] = a[ y ][ x ] = ;
}
int t ;
scanf( "%d" , &t ) ;
for( int i = ; i <= n ; i ++ ) a[ i ][ i ] = a[ i ][ ] = ;
a = power( a , t ) ;
int ans = ;
for( int i = ; i <= n ; i ++ ) {
ans = ( ans + a[ ][ i ] ) % mod ;
}
printf( "%d\n" , ans ) ;
}