每日一个冷知识：题解第一个方法又双叒叕过不了。

思路

题目要求求方案数，又有$N\leq 30$，不难想到DP。设计状态$f_{i,j}$表示第$j$秒的时候到达城市$i$一共有多少种方案数，转移方程只需沿着边加起来就行了。最终的答案就是每一秒到达每一个城市的和（之所以是每一秒是因为可以自爆）。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10,P=2017;
int f[33][N],n,m,t;
vector<int>G[33];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	scanf("%d",&t);
	f[1][0]=1;
	for(int i=0;i<t;i++)for(int j=1;j<=n;j++)
	{
		f[j][i+1]=(f[j][i+1]+f[j][i])%P;
		for(int w:G[j])
		{
			f[w][i+1]=(f[w][i+1]+f[j][i])%P;
		}
	}
	int ans=1;
	for(int i=1;i<=n;i++)for(int j=1;j<=t;j++)ans=(ans+f[i][j])%P;
	printf("%d\n",ans);
	return 0;
}

但是一交，RE了，仔细一看，内存限制只有125MiB（每日出题人恶趣味）。

既然RE不妨考虑滚动数组优化（本蒟蒻滚动数组不是很擅长，代码稍微难看了一点），很ez的拿下AC

AC代码

#include<bits/stdc++.h>
using namespace std;
const int P=2017;
int f[33][2],n,m,t;
vector<int>G[33];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1,x,y;i<=m;i++)
	{
		scanf("%d%d",&x,&y);
		G[x].push_back(y);
		G[y].push_back(x);
	}
	scanf("%d",&t);
	f[1][0]=1;int ans=1;
	for(int i=0;i<t;i++)for(int j=1;j<=n;j++)
	{
		f[j][(i&1)^1]=(f[j][(i&1)^1]+f[j][i&1])%P;//可以停留在原地 
		ans=(ans+f[j][i&1])%P;
		for(int w:G[j])
		{
			f[w][(i&1)^1]=(f[w][(i&1)^1]+f[j][i&1])%P;
			ans=(ans+f[j][i&1])%P;//贡献在循环内部计算，方便计算 
		}
		f[j][i&1]=0;
	}
	printf("%d\n",ans);
	return 0;
}

这篇代码虽然没有矩阵乘法的巨巨快，但是很好理解，好想，代码还好打（主要是我想不到矩阵乘法ToT）。

分层图DP

我做这题本来是冲着它那个“倍增”标签来的，结果进来一看，哟，不是标准的分层图DP嘛，愉快地敲起了代码，20分种，感谢我们可爱的氧气同志和评测机同志，痛快地AC了这题

分层图大家应该都知道（这其实就是DP），通常状态是：

$f[j][u][...]$代表在第$j$时刻，在节点$u$,然后状态为$...$的最优化/计数等

这道题就是个朴素的分层图DP，

$f[j][u]$表示第$j$时刻，在节点$u$的情况数

然后是处理爆炸。当然我们可以加入状态，但是为了后面更好地做矩阵乘法，我们决定把他搬到生活中来

一个机器人，如果它选择了死亡，那么这将是它一个有去无回的路，一个不可逆转的路，它将永远呆在里面……

对就是这样！这是个有去无回的单向边！爆炸的死亡节点的路是无法逆转的！

好的，我们创建一个死亡节点$n+1$，所有点连向它，然而它不能连向别人

#include<bits/stdc++.h>
using namespace std;
const int N=39,M=109; 
struct edge{int to,nxt;}e[(M+N)<<1]; int hd[N],tot;
void add(int u,int v){
	e[++tot]=(edge){v,hd[u]}; hd[u]=tot;
}
int n,m,t,ans,f[1000002][32];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),add(u,v),add(v,u);
	scanf("%d",&t);
	for(int i=1;i<=n;i++) add(i,n+1),add(i,i); f[0][1]=1; add(n+1,n+1);
	for(int j=0;j<=t;j++){
		for(int u=1;u<=n+1;u++){
			for(int i=hd[u];i;i=e[i].nxt){
				f[j+1][e[i].to]=(f[j+1][e[i].to]+f[j][u])%2017; 
			}
		}
	}
	for(int i=1;i<=n+1;i++) ans=(ans+f[t][i])%2017;
	printf("%d",ans);
	return 0;
}

（注：如果$f$数组再开大一点就会MLE，所以嘛。。。）

精益求精--矩阵乘法

经过氧气同志和评测机同志的不懈努力下，我们AC了这个题目

可是我们要有职业精神，取得更好的成绩，而不是依赖于我们的好朋友氧气和评测机

我们再看一眼转移方程：

f[j+1][e[i].to]=(f[j+1][e[i].to]+f[j][u])%2017;

你看到了什么？常系数线性变换！而且$n\le 30$ ！这是矩阵乘法的标志!

推一下就知道，转移矩阵其实就是我们的邻接矩阵，于是，修改过的邻接矩阵做一个矩阵快速幂就好了

其实，我们可以看到，这道题就是传球游戏的一个变种，我们只需要加入死亡节点之后，一切就变得简单无比了

然后我们为了简化一下矩阵（其实也没多少），死亡节点变成$0$号节点

#include<bits/stdc++.h>
using namespace std;
int n,m,t,ans;
struct mat{ //朴素矩阵 
	int a[33][33];
	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;
mat pow(mat a,int p){ //朴素快速幂 
	if(p==0) return I;
	if(p==1) return a;
	mat tmp=pow(a*a,p/2);
	if(p%2) return tmp*a;
	else return tmp;
}
int main(){
	scanf("%d%d",&n,&m,&t);
	for(int i=1,u,v;i<=m;i++) scanf("%d%d",&u,&v),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; //新边和单位矩阵 
	scanf("%d",&t); ansm=pow(E,t); //矩阵快速幂 
	for(int i=0;i<=n;i++) ans+=ansm.a[1][i]; //统计答案 
	printf("%d",ans%2017);
	return 0;
}

其实这份代码除了两行添加新边和统计答案，全部都是邻接矩阵快速幂的模板，所以其实这种题型需要更加熟练才行，说不定下次氧气和评测机就拯救不了你了呢