算法

(矩阵快速幂) $O(N^3 \log K)$

假设从 $u$ 出发，到 $v$ 的长度为 $k$ 的路径的总数为 $G_k[u][v]$。首先，$k=1$ 时值和边数相等，因此 $G_1$ 就等于图的邻接矩阵。假设我们已经得到了 $G_{k_1}$ 和 $G_{k_2}$，则有

$$ G_{k_1 + k_2}[u][v] = \sum_{w=1}^n G_{k_1}[u][w] \times G_{k_2}[w][v] $$

表示成矩阵的乘积的形式即为

$$ G_{k_1 + k_2} = G_{k_1}G_{k_2} $$

因此，可以使用矩阵的幂表示出

$$ G_k = G_1^k $$

类似题： ラムドスウイルスの感染拡大-hard 【 题解 】

C++ 代码

#include <bits/stdc++.h>
#if __has_include(<atcoder/all>)
#include <atcoder/all>
using namespace atcoder;
#endif
#define rep(i, n) for (int i = 0; i < (n); ++i)

using namespace std;
using ll = long long;
using mint = modint1000000007;

template<typename T>
struct Matrix {
  int h, w;
  vector<vector<T>> d;
  Matrix() {}
  Matrix(int h, int w, T val=0): h(h), w(w), d(h, vector<T>(w,val)) {}
  Matrix& unit() {
    assert(h == w);
    rep(i,h) d[i][i] = 1;
    return *this;
  }
  const vector<T>& operator[](int i) const { return d[i];}
  vector<T>& operator[](int i) { return d[i];}
  Matrix operator*(const Matrix& a) const {
    assert(w == a.h);
    Matrix r(h, a.w);
    rep(i,h)rep(k,w)rep(j,a.w) {
      r[i][j] += d[i][k]*a[k][j];
    }
    return r;
  }
  Matrix pow(long long t) const {
    assert(h == w);
    if (!t) return Matrix(h,h).unit();
    if (t == 1) return *this;
    Matrix r = pow(t>>1);
    r = r*r;
    if (t&1) r = r*(*this);
    return r;
  }
};

int main() {
    int n; ll k;
    cin >> n >> k;

    Matrix<mint> d(n, n);
    rep(i, n)rep(j, n) {
        int a;
        cin >> a;
        d[i][j] = a;
    }
    d = d.pow(k);

    mint ans;
    rep(i, n)rep(j, n) ans += d[i][j];
    cout << ans.val() << '\n';

    return 0;
}