题目描述

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

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

这个可乐机器人有三种行为,分别是:

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

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

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


输入格式

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

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

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


输出格式

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

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


Input & Output ‘s examples

Input ‘s eg

3 2
1 2
2 3
2

Output ‘s eg

8

数据范围与约定

对于 $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;
}

THE END