洛谷P3758 可乐

传送门

题目描述

加里敦星球的人们特别喜欢喝可乐。因而，他们的敌对星球研发出了一个可乐机器人，并且放在了加里敦星球的 11 号城市上。这个可乐机器人有三种行为： 停在原地，去下一个相邻的城市，自爆。它每一秒都会随机触发一种行为。现在给加里敦星球城市图，在第 00 秒时可乐机器人在 11 号城市，问经过了 tt 秒，可乐机器人的行为方案数是多少？

输入格式

第一行输入两个正整数 NN，MM。NN 表示城市个数，MM 表示道路个数。

接下来 MM 行每行两个整数 uu，vv，表示 uu，vv 之间有一条道路。保证两座城市之间只有一条路相连，且没有任何一条道路连接两个相同的城市。

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

输出格式

输出可乐机器人的行为方案数，答案可能很大，请输出对 20172017 取模后的结果。

输入输出样例

输入 #1复制
3 2
1 2
2 3
2
输出 #1复制
8

说明/提示

样例输入输出 1 解释

• 11 ->爆炸。
• 11 -> 11 ->爆炸。
• 11 -> 22 ->爆炸。
• 11 -> 11 -> 11。
• 11 -> 11 -> 22。
• 11 -> 22 -> 11。
• 11 -> 22 -> 22。
• 11 -> 22 -> 33。

数据范围与约定

对于 20%20% 的数据，保证 t \leq 1000t≤1000。
对于100%100%的数据，保证 1 < t \leq 10^61 6
，1 \leq N \leq301≤N≤30，0 < M < 1000

上代码：

#include 
#include 

int matrix[31][31],tem[31][31],ans[31][31],n,m,T,s,t;
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d%d",&s,&t);
		matrix[s][t]=matrix[t][s]=1;
	}
	scanf("%d",&T);
	for(int i=0;i<=n;i++)matrix[i][0]=matrix[i][i]=1,ans[i][i]=1;
	while(T){
		if(T&1){
			for(int i=0;i<=n;i++)
				for(int j=0;j<=n;j++)
					for(int k=0;k<=n;k++)
						tem[i][j]=(tem[i][j]+ans[i][k]*matrix[k][j])%2017;
			for(int i=0;i<=n;i++)
				for(int j=0;j<=n;j++)
					ans[i][j]=tem[i][j],tem[i][j]=0;
		}
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++)
				for(int k=0;k<=n;k++)
					tem[i][j]=(tem[i][j]+matrix[i][k]*matrix[k][j])%2017;
		for(int i=0;i<=n;i++)
			for(int j=0;j<=n;j++)
				matrix[i][j]=tem[i][j],tem[i][j]=0;
		T>>=1;
	}
	int fin=0;
	for(int i=0;i<=n;i++)fin=(fin+ans[1][i])%2017;
	printf("%d\n",fin);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35