题目描述

加里敦星球的人们特别喜欢喝可乐。

因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的 $1$ 号城市上。

这个可乐机器人有三种行为，分别是：

停在原地
去下一个相邻的城市
自爆

它每一秒都会随机触发一种行为。现在给加里敦星球城市图，在第 $0$ 秒时可乐机器人在 $1$ 号城市。

问经过了 $t$ 秒，可乐机器人的行为方案数是多少？

输入格式

第一行输入两个正整数 $n , m$，分别表示城市个数与道路个数。

接下来 $m$ 行每行两个整数 $u,v$，表示 $u,v$ 之间有一条道路。

最后一行是一个整数 $t$，表示经过的时间。

输出格式

输出可乐机器人的行为方案数。

答案可能很大，请输出对 $2017$ 取模后的结果。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

数据范围与约定

对于 $20\%$ 的数据，保证 $1 \leq t \leq 1000$。

对于 $100\%$ 的数据，保证 $1 \leq t \leq 10^6$ ，$1 \leq n \leq 30$，$0 < m < 100$，$1 \leq u, v \leq n$。

分析

矩阵乘法的简单应用。

读完题发现 $n$ 很小，可以使用邻接矩阵存图。

考虑邻接矩阵幂的意义。

设该邻接矩阵为 $A$ ，则 $A^k$ 中，第 $i$ 行第 $j$ 列表示从点 $i$ 到点 $j$ 经过恰好 $k$ 步的方案数。

这样的话，我们只需要将邻接矩阵 $A$ 建出来，之后用矩阵快速幂计算 $A^k$ ，最后统计 $\sum_{i = 1}^n A[1][i]$ 即可。

但问题来了，原地停留和自爆如何处理？

原地停留的话，我们只需要将每个点向自己连一条边即可。

而自爆的话，我们可以将每个点向一个超级汇点连一条边，而这个超级汇点本身没有任何出边。这样的话就满足了一个点随时可以自爆同时无法回到之前的状态

时间复杂度为 $O(l^3 \log t)$，其中 $l$ 为邻接矩阵的边长。在本题中 $l = n$，足以通过 $100\%$ 的数据。

细节部分见代码即可。

Code[Accepted]

#include <algorithm>
#include <iostream>
#include <cstring>
#include <iomanip>
#include <cstdlib>
#include <sstream>
#include <cstdio>
#include <string>
#include <vector>
#include <cctype>
#include <stack>
#include <queue>
#include <deque>
#include <cmath>
#include <map>
#include <set>

#define I inline
#define db double
#define ll long long
#define pb push_back
#define MP make_pair
#define ldb long double
#define ull unsigned long long
#define PII pair<int , int>
#define PIL pair<int , long long>
#define PSL pair<string , long long>
#define PLL pair<long long , long long>
#define all(x) (x).begin() , (x).end()
#define copy(a , b) memcpy(a , b , sizeof(b))
#define clean(a , b) memset(a , b , sizeof(a))
#define rep(i , l , r) for (int i = (l); i <= (r); i ++)
#define per(i , r , l) for (int i = (r); i >= (l); i --)
#define PE(i , x) for(int i = head[x]; i; i = edge[i].last)
#define DEBUG(x) std :: cerr << #x << '=' << x << std :: endl

using namespace std;

const int N = 10001;
const int M = 100001;
const int HA = 2017;
const int INF = 2047483647;
const long long INFL = 9023372036854775807;

struct Matrix{
    ll data[45][45];
};

Matrix A;

Matrix operator * (const Matrix &A , const Matrix &B){
    Matrix C; clean(C.data , 0);
	
    rep(i , 0 , 30){
        rep(j , 0 , 30){
    	    rep(k , 0 , 30){
                C.data[i][j] += A.data[i][k] * B.data[k][j];
    	        C.data[i][j] %= HA;
    	    }
    	}
    }
    return C;
}

Matrix Pow(Matrix A , ll k){
    Matrix B; clean(B.data , 0);
    rep(i , 0 , 30) B.data[i][i] = 1;
	
    while(k){
    	if(k & 1){
    	    B = B * A;
    	}	
    	A = A * A;
    	k >>= 1;
    }
    return B;
}

int main() {
    #ifdef LOCAL
        freopen("try.in" , "r" , stdin);
        freopen("try1.out" , "w" , stdout);
    #endif
    int n , m , u , v;
    scanf("%d%d" , &n , &m);
    rep(i , 1 , m){
    	scanf("%d%d" , &u , &v);
    	A.data[u][v] = A.data[v][u] = 1;
    }	   
    A.data[0][0] = 1;
    rep(i , 1 , n){
    	A.data[i][0] = 1;
    	A.data[i][i] = 1;
    }
    int tim; scanf("%d" , &tim);
    Matrix ans = Pow(A , tim);
    ll res = 0;
    rep(i , 0 , n){
    	res += ans.data[1][i];
    	res %= HA;
    } 
    printf("%lld\n" , res);

    return 0;
}