题面传送门 考虑暴力建分层图dp 实际上就是对于每个时间建到下一层的图就好了。 然后停留就是自环，爆炸就连向永远走不出来的点。 其实这个东西是可以矩乘优化的。 然后复杂度就降到 O ( l o g t n 3 ) O(logtn^3) O(logtn3) 代码实现:
#include<cstdio> #define mod 2017 using namespace std; int n,m,k,x,y,z,t,anss; struct jz{ long long f[139][139]; jz operator *(const jz &x)const{ register int i,j,k;jz s; for (i=0;i<=n;i++) for (j=0;j<=n;j++) s.f[i][j]=0; for(i=0;i<=n;i++){ for(j=0;j<=n;j++){ for(k=0;k<=n;k++){ s.f[i][j]+=f[i][k]*x.f[k][j]%mod;s.f[i][j]%=mod; } } } return s; } }g,ans; int main(){ register int i; scanf("%d%d",&n,&m); for(i=1;i<=m;i++)scanf("%d%d",&x,&y),g.f[x][y]=g.f[y][x]=1; for(i=0;i<=n;i++) g.f[i][i]=g.f[i][0]=1; scanf("%d",&y); ans=g;y--; while(y){ if(y&1)ans=ans*g; g=g*g;y>>=1; } for(i=0;i<=n;i++) anss+=ans.f[1][i]; printf("%d\n",anss%mod); }