邻接矩阵的 K 次幂

设A（n x n）为一个图的邻接矩阵，则a(i,j)表示两个点之间是否连通（1：连通，0：不连通）。那么A的k次方中的每一个a（i，j）表示点i和j之间长度为k的路的条数。假设一个图能划分成若干个子图，每个子图之间不相连，那么A^1 +A2+…+An能表示该图的连通性。为0则不可能在一个子图，为非0则可以在一个子图

矩阵快速幂

矩阵快速幂即在整数快速幂的基础上加入了矩阵运算, 使得 算 矩阵 A ^ n 的复杂度降为 log(n)
例题: Different Pass a Ports
问固定时间后有多少种走法，直接矩阵快速幂（可以求出长度为固定值的路径有多少条）

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define IOS ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
#define fr(qa, ws, ed) for (int qa = (ws); qa <= (ed); ++qa)

const int N = 1e6 + 1000, mod = 1e9+7;
using ll = long long;
struct matrix{
    int x, y;
    ll MM[110][110];
    // 矩阵的初始化
    matrix(int xx, int yy, int aa = 0) : x(xx), y(yy)
    {
        for (int i = 1; i <= xx; ++i)
            for (int j = 1; j <= yy; ++j)
                MM[i][j] = (i == j) * aa;
    }
    // 矩阵乘法
    matrix operator * (const matrix &A) const {
        matrix temp(x, A.y);
        for (int i = 1; i <= x; ++i)
            for (int j = 1; j <= A.y; ++j)
                for (int k = 1; k <= y; ++k)
                    temp.MM[i][j] = (temp.MM[i][j] + (MM[i][k] * A.MM[k][j] % mod)) % mod;
        return temp;
    }
    // 矩阵快速幂 res 为单位矩阵, 求 (*this) ^ k 
    matrix operator ^ (ll k) {
        matrix res(this->x, this->y, 1);
        matrix tt = *this;
        while (k)
        {
            if (k & 1) res = res * tt;
            k >>= 1, tt = tt * tt;
        }
        return res;
    }
};
int main()
{
    IOS
    int n, m, k; cin >> n >> m >> k;
    matrix a(n, n);
    fr (i, 1, m)
    {
        int x, y; cin >> x >> y;
        a.MM[x][y] += 1;
        a.MM[y][x] += 1;
    }
    a = a ^ k;
    ll ans = 0;
    fr (i, 1, n) ans = (ans + a.MM[1][i]) % mod;

    cout << ans << endl;
    return 0;
}