[数论]矩阵快速幂

注意

• 矩阵下标从1开始

说明

• 用于计算 $$Mat^k$$(Mat的k次幂)
• k为int 或 long long

使用说明

1. 输入矩阵边界n(1--n)*(1--n)
2. 输入幂次num;
3. 输入矩阵Mat.a[i][j];
4. 计算:Mat=Mat^num;
5. 输出

模板

typedef long long ll;
const int mod = 1e9 + 7;
const int MAX_MATRIX_NUM_N = 100 + 10;
const int MAX_MATRIX_NUM_M = 100 + 10;
ll n, num;

struct Matrix
{
    ll a[MAX_MATRIX_NUM_N][MAX_MATRIX_NUM_M];

    Matrix operator * (const Matrix &b) const
    {
        Matrix res = b;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
            {
                res.a[i][j] = 0;
                for (int k = 1; k <= n; k++)
                    res.a[i][j] = (res.a[i][j] + a[i][k] * b.a[k][j] % mod) % mod;
            }
        return res;
    }

    friend Matrix operator ^ (Matrix x, ll num)
    {
        Matrix res = x;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                res.a[i][j] = (i == j);
        while (num)
        {
            if (num & 1)res = res* x;
            x = x* x;
            num >>= 1;
        }
        return res;
    }

};
Matrix Mat;

int main()
{
    scanf("%lld %lld", &n, &num);
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            scanf("%d", &Mat.a[i][j]);
    Mat = Mat^num;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
            printf("%d ", Mat.a[i][j]);
        printf("\n");
    }
}