题目描述
加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的 (1) 号城市上。这个可乐机器人有三种行为： 停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。现在给加里敦星球城市图，在第 (0) 秒时可乐机器人在 (1) 号城市，问经过了 (t) 秒，可乐机器人的行为方案数是多少？
输入格式
第一行输入两个正整数 (N)，(M)。(N) 表示城市个数，(M) 表示道路个数。
接下来 (M) 行每行两个整数 (u)，(v)，表示 (u)，(v) 之间有一条道路。保证两座城市之间只有一条路相连。
输出格式
输出可乐机器人的行为方案数，答案可能很大，请输出对 (2017) 取模后的结果。
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=32;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}int n,m;
struct mat{
int a[N][N];
mat(){memset(a,0,sizeof(a));}
mat operator *(const mat b)const{
mat c;
for(int i=0;i<=n;i++)
for(int j=0;j<=n;j++)
for(int k=0;k<=n;k++)
c.a[i][j]=(c.a[i][j]+a[i][k]*b.a[k][j])%2017;
return c;
}
}I,E,ansm;
inline mat ksm(mat a,int y){
mat res=I;
while(y){
if(y&1)res=res*a;
a=a*a; y>>=1;
}
return res;
}
signed main(){
cin>>n>>m;
for(int i=1,u,v;i<=m;i++){
u=read(),v=read();
E.a[u][v]=E.a[v][u]=1;
}
for(int i=0;i<=n;i++) I.a[i][i]=E.a[i][i]=1,E.a[i][0]=1;
int t=read(),ans=0;
ansm=ksm(E,t);
for(int i=0;i<=n;i++)ans=(ans+ansm.a[1][i])%2017;
printf("%d
",ans);
}