题解 P5789 【[TJOI2017]可乐（数据加强版）】
Kevin_Zhen
·
·
题解
题目链接 \mathfrak{P5789}。
可能更好的阅读体验。
前置知识
邻接矩阵 A 的幂的意义：
对于最初的邻接矩阵 $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$ 条边的路径数。
[参考博客](http://www.matrix67.com/blog/archives/276)。
### 解题思路
对于停在原地的操作，不妨令每座城市连一条自环，理解为走过这条边后回到自己。
对于爆炸操作，不妨令每座城市连一条**单向边**指向 $0$ 号结点，并使 $0$ 号结点**有且仅有**一条出边指向自己，理解为机器人走到 $0$ 号城市，然后在那不停兜圈。
问题转变为机器人每一秒**必须**走过一条边，求 $t$ 秒后的行为方案数。
求出 $A^t$，然后记录 $ans=\sum\limits_{i=0}^n{A^t}_{1,i}$ 即可。
**注意**：$0$ 号城市的自环是必需的。因为 $A^k$ 记录的是**恰好**经过 $k$ 条边。
### AC CODE
```cpp
#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;
}
```