AT4539 Walk

• 题意：给一张有向简单图，给出邻接矩阵，求长度为 \(K\) 的路径条数，答案对 \(10^9+7\) 取模。
• 题解：
• 代码：

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <bitset>
#include <iostream>
#include <unordered_map>
#include <queue>
#include <vector>
using namespace std;
typedef long long ll;
const ll N = 55;
ll mod = 1e9 + 7;
const ll maxn = 110;
ll n;
struct Matrix {
    ll a[N][N];
    Matrix (){memset(a, 0, sizeof a);}
    Matrix operator*(Matrix rhs) const{
        Matrix ret;
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                for (int k = 0; k < n; k ++) {
                    (ret.a[i][j] += a[i][k] * rhs.a[k][j]) %= mod;
                }
            }
        }
        return ret;
    }
};
Matrix q_pow(Matrix A, ll k) {
    Matrix ret = A;
    k--;
    if (k <= 0)return ret;
    while (k) {
        if (k & 1) {
            ret = ret * A;
        }
        k >>= 1;
        A = A * A;
    }
    return ret;
}

void solve() {
    Matrix A;
    ll  k;
    cin >> n >> k;
    for (int i = 0; i < n; i ++) {
        for (int j = 0; j < n; j ++) {
            cin >> A.a[i][j];
        }
    }
    A = q_pow(A, k);
    ll ans = 0;
    for (int i = 0; i < n; i ++) {
        for (int j = 0 ; j < n; j ++) {
            (ans += A.a[i][j]) %= mod;
        }
    }
    cout << ans << endl;
}
signed main() {
    ll t = 1;
    while (t--) solve();
    return 0;
}

AT4539 Walk

原文：https://www.cnblogs.com/Xiao-yan/p/14609242.html