Ta nhận được đồ thị ~G~ được biểu diễn dưới dạng ma trận kề ~a~ và ta muốn tính số đường đi có độ dài ~K~. Đầu tiên, ta chuyển ~a~ sang ma trận ~m~.

Nhận thấy rằng khi ta nhân ~m~ với ~m~, ta nhận được số lượng đường đi với độ dài ~2~ giữa từng cặp đỉnh ~i, j~. Vậy nếu với ma trận ~m^p~, ta sẽ có số đường đi độ dài ~p~ với từng cặp đỉnh ~i, j~.

Như vậy, thứ chúng ta đang tìm là ~m^K~ và có thể được tính bằng cách nhân ma trận và dùng kĩ thuật chia để trị để tính lũy thừa nhanh.

Độ phức tạp: ~\mathcal{O}(N^3\log{}K)~

Code mẫu

#include <bits/stdc++.h>

using namespace std;

const int MOD = 1e9 + 7;

int add(int i, int j) {
    i += j;
    if (i >= MOD) i -= MOD;
    return i;
}
int mul(int i, int j) {
    return int((long long) i * j % MOD);
}

struct Matrix{
    int m[50][50];
};

Matrix MatrixMultiplication(Matrix a, Matrix b) {
    Matrix res;
    memset(res.m, 0, sizeof(res.m));

    for (int i = 0; i < 50; i++) {
        for (int j = 0; j < 50; j++) {
            for (int k = 0; k < 50; k++) { 
                res.m[i][j] = add(res.m[i][j], mul(a.m[i][k], b.m[k][j]));
            }
        }
    }

    return res;
}

Matrix MatrixPower(Matrix a, long long k) {
    Matrix res;
    memset(res.m, 0, sizeof(res.m));
    for (int i = 0; i < 50; i++) res.m[i][i] = 1;

    while (k > 0) {
        if (k & 1) res = MatrixMultiplication(res, a);
        a = MatrixMultiplication(a, a);
        k >>= 1;
    }

    return res;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);

    int n; long long k;
    cin >> n >> k;
    Matrix a;
    memset(a.m, 0, sizeof(a.m));
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cin >> a.m[i][j];
        }
    }

    a = MatrixPower(a, k);
    int ans = 0;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            ans = add(ans, a.m[i][j]);
        }
    }
    cout << ans;
}