题意
给定一个无向图，求路径长度为 \(k\) 的路径条数。
\(n \le 50\)。
Sol
考虑 \(dp\)，设 \(f_{i, j}\) 表示从 \(i \to j\) 的路径长为 \(k\) 的方案数。
不难发现转移即为矩阵乘法。
直接快速幂即可。
Code
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <array>
#define int long long
using namespace std;
#ifdef ONLINE_JUDGE
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 23], *p1 = buf, *p2 = buf, ubuf[1 << 23], *u = ubuf;
#endif
int read() {
int p = 0, flg = 1;
char c = getchar();
while (c < '0' || c > '9') {
if (c == '-') flg = -1;
c = getchar();
}
while (c >= '0' && c <= '9') {
p = p * 10 + c - '0';
c = getchar();
}
return p * flg;
}
void write(int x) {
if (x < 0) {
x = -x;
putchar('-');
}
if (x > 9) {
write(x / 10);
}
putchar(x % 10 + '0');
}
const int N = 55, mod = 1e9 + 7;
void Mod(int &x) {
if (x >= mod) x -= mod;
if (x < 0) x += mod;
}
struct Matrix {
int A[N][N];
int n, m;
int* operator [](int x) {
return A[x];
}
Matrix (int n_, int m_) {
for (int i = 1; i <= n_; i++)
for (int j = 1; j <= m_; j++)
A[i][j] = 0;
n = n_, m = m_;
}
Matrix (int n_, int m_, int flg) {
for (int i = 1; i <= n_; i++)
for (int j = 1; j <= m_; j++)
A[i][j] = 0;
for (int i = 1; i <= n_; i++)
A[i][i] = 1;
n = n_, m = m_;
}
friend Matrix operator *(Matrix a, Matrix b) {
Matrix ans(a.n, b.m);
for (int i = 1; i <= a.n; i++)
for (int j = 1; j <= a.m; j++)
for (int k = 1; k <= b.m; k++)
ans[i][j] += a[i][k] * b[k][j] % mod, Mod(ans[i][j]);
return ans;
}
friend Matrix operator ^(Matrix x, int k) {
Matrix ans(x.n, x.m, 1);
while (k) {
if (k & 1) ans = ans * x;
x = x * x;
k >>= 1;
}
return ans;
}
};
signed main() {
int n = read(), k = read();
Matrix T(n, n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
T[i][j] = read();
T = T ^ k;
int ans = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
ans += T[i][j], Mod(ans);
write(ans), puts("");
return 0;
}