定义
阶为(n)的图(G)的邻接矩阵(A)是(n imes n)的。将(G)的顶点标签为(v_1,v_2,...,v_n)。若((v_i,v_j) in E(G))，(A_{ij}=1)，否则(A_{ij}=0)。也可以用大于0的值表示边的权值，例如可以用边权值表示一个点到另一个点的距离。
特性
设图(G)的邻接矩阵为(A)，边的取值为1。
- 如果顶点有自我连接产生的自环，则在矩阵的主对角线上会有非零的值；如果没有自环，则主对角线上全部是0。
- (A^n)的元素(A^n_{ij})可以表示由顶点(i)到顶点(j)长度为(n)的径的数目。
- (G)没有有向圈若且唯若 $ I-A$可逆。 ((IA)^{-1})的元素(ij)表示由顶点(i)到顶点(j)的所有径的数目。因为：$ (I-A)^{-1} = I A A^2 A^3 ... $
以上内容来自维基百科需珂学上网
这道题就是利用了第二个特性
如果单纯考虑走的话，大那就是(sumlimits_{i=1}^{n}A[1][i])
那么如何考虑不动和爆炸的情况呢？
不动简单，我要给每个节点连上自环，这样就相当于不动了
那么爆炸呢？
爆炸需要满足两个条件
- 爆炸不能够还原
- 所有点都随时能够选择爆炸
这样我们就可以把所有点连接到一个点（虚拟的）上去，这个点除了自己连边外不连其他边
这样就满足了上面的两个条件
/*
@ author:pyyyyyy
-----思路------
-----debug-------
*/
#include<bits/stdc++.h>
using namespace std;
const int N=50;
const int mod=2017;
struct Matrix
{
int m[N][N];
}a,ans;
Matrix mul(Matrix x,Matrix y)
{
Matrix c;
memset(c.m,0,sizeof(c.m));
for(int i=0;i<=100;++i)
for(int j=0;j<=100;++j)
for(int k=0;k<=100;++k)
c.m[i][j]=(c.m[i][j]+x.m[i][k]*y.m[k][j])%mod;
return c;
}
Matrix ksm(Matrix &a,int b)
{
Matrix ret;
memset(ret.m,0,sizeof(ret.m));
for(int i=1;i<=100;++i) ret.m[i][i]=1;
while(b)
{
if(b&1) ret=mul(ret,a);
a=mul(a,a);
b>>=1;
}
return ret;
}
int n,m,t;
void add(int u,int v)
{
a.m[u][v]=1;
}
int main()
{
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
cin>>n>>m;
for(int i=1;i<=m;++i)
{
int u,v;
scanf("%d%d",&u,&v);
add(u,v);add(v,u);
}
for(int i=0;i<=n;++i) add(i,i);
for(int i=1;i<=n;++i) add(i,0);
cin>>t;
Matrix cnt=ksm(a,t);
int ans=0;
for(int i=0;i<=n;++i) ans=(ans+cnt.m[1][i])%mod;
cout<<ans;
return 0;
}
还有一个加强版，只要把上述代码的数值和循环之类的变大就可以过了