题目来源：AtCoder EDU DP题集
题目链接：Here
单独拎出来是因为这道题是一个很好的板子，值得记录
题意
给定一个 n 个节点的有向图的邻接矩阵，求该有向图中长度为 k 的路径长。
解法
算法涉及：倍增 Floyd
答案为该邻接矩阵的 \(k\) 次幂的行列式。
学过离散数学的后面图论的话大概都知道求有向图中长度为 \(k\) 的路径长的路径与原始图的 \(k\) 次方相关，所以只需要求原矩阵的 \(k\) 次幂即可
使用矩阵快速幂即可，时间复杂度 \(\mathcal{O}(n^2log k)\)
const int mod = 1e9 + 7;
ll n, k;
struct Matrix {
ll mat[50][50];
void clear() {memset(mat, 0, sizeof(mat));}
void reset(int n) {
clear();
for (int i = 0; i < n; ++i) mat[i][i] = 1;
}
} a;
Matrix MatrixMul(Matrix a, Matrix b) { // 矩阵快速乘
Matrix t; t.clear();
for (int i = 0; i < n; ++i)
for (int k = 0; k < n; ++k)
for (int j = 0; j < n; ++j)
t.mat[i][j] = (t.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % mod;
return t;
}
ll MatrixQpow(Matrix a, ll p) { // 矩阵快速幂
Matrix s; s.reset(n);
for (; p; p >>= 1, a = MatrixMul(a, a))
if (p & 1) s = MatrixMul(s, a);
ll sum = 0;
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j)
sum = (sum + s.mat[i][j]) % mod;
return sum;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> k;
for (int i = 0; i < n; ++i) for (int j = 0; j < n; ++j) cin >> a.mat[i][j];
cout << MatrixQpow(a, k);
}