自动搬运

查看原文

来自洛谷，原作者为

	Kevin_Zhen 不再回来

搬运于2025-08-24 22:14:24，当前版本为作者最后更新于2021-08-24 11:35:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接 $\mathfrak{P5789}$。
可能更好的阅读体验。

前置知识

邻接矩阵 $A$ 的幂的意义：
$A^k$ 记录图上任意两点 $u$ 到 $v$ 恰好经过 $k$ 条边的路径数。

对于最初的邻接矩阵 $A$，$A_{i,j}=1$ 当且仅当存在一条边 $i\Rightarrow j$。注意这里“当且仅当”的含义，如果 $A_{i,j}=1$ 且 $A_{j,k}=1$，但 $i$ 和 $k$ 两点之间没有一条边直接相连，此时的 $A_{i,k}=0$。那么换一个角度理解，$A$ 记录着图上任意两点 $u$ 到 $v$ 恰好经过 $1$ 条边的路径数。
此时我们令矩阵 $C=A\times A$，由矩阵乘法可知 $C_{i,j}=\sum\limits_{k=1}^n A_{i,k}\times A_{k,j}$，实际上就等于枚举以 $k$ 为中转点，从点 $i$ 到点 $j$ 恰好经过 $2$ 条边的路径数。同理，如果要求经过 $3$ 条边，计算 $C\times A$，即 $A^3$ 即可。那么普适地，$A^k$ 记录图上任意两点 $u$ 到 $v$ 恰好经过 $k$ 条边的路径数。

参考博客。

解题思路

对于停在原地的操作，不妨令每座城市连一条自环，理解为走过这条边后回到自己。
对于爆炸操作，不妨令每座城市连一条单向边指向 $0$ 号结点，并使 $0$ 号结点有且仅有一条出边指向自己，理解为机器人走到 $0$ 号城市，然后在那不停兜圈。
问题转变为机器人每一秒必须走过一条边，求 $t$ 秒后的行为方案数。
求出 $A^t$，然后记录 $ans=\sum\limits_{i=0}^n{A^t}_{1,i}$ 即可。

注意：$0$ 号城市的自环是必需的。因为 $A^k$ 记录的是恰好经过 $k$ 条边。

AC CODE

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int maxn = 110;
const int Mod = 2017;

struct Matrix {
	int a[maxn][maxn], n, m;
	int* operator [](int x) { return a[x]; }
	void clear() { n = 0, m = 0, memset(a, 0, sizeof(a)); }
} a;

Matrix operator *(Matrix &x, Matrix &y) {
	Matrix z; z.clear(); z.n = x.n, z.m = y.m;
	for (int i = 0; i <= x.n; ++i) {
		for (int j = 0; j <= x.m; ++j) {
			for (int k = 0; k <= y.m; ++k) z[i][k] = (z[i][k] + x[i][j] * y[j][k]) % Mod;
		}
	}
	return z;
}

Matrix qpow(Matrix &base, int p) {
	Matrix res = base; --p;
	while (p) {
		if (p & 1) res = res * base;
		base = base * base;
		p >>= 1;
	}
	return res;
}

int n, m, t, ans;

int main() {
	scanf("%d%d", &n, &m); a.n = n, a.m = n;
	for (int i = 0; i <= n; ++i) a[i][i] = 1, a[i][0] = 1;
	for (int i = 1; i <= m; ++i) {
		int u, v; scanf("%d%d", &u, &v);
		a[u][v] = 1; a[v][u] = 1;
	}
	scanf("%d", &t);
	a = qpow(a, t); for (int i = 0; i <= n; ++i) ans = (ans + a[1][i]) % Mod;
	printf("%d", ans);
	return 0;
}