前言

这个算法是很久很久之前我学习的,最近在Luogu看到了一题矩阵加速递推的斐波那契数列居然是绿题...

正文

我们需要先了解一下矩阵是一个什么东西。

矩阵

在数学中,矩阵(Matrix)是一个按照长方阵列排列的复数或实数集合。
我们来了解一下矩阵乘法:
A * B
如果矩阵A是m×n的,矩阵B是n×p,那么他们的乘积C是m×p的,它的元素:
矩阵乘法

快速幂

学习快速幂请去我的另外一篇文章快速幂 (Exponentiation By Squaring).

矩阵快速幂

这是一篇大水文,我们只需要把快速幂的乘法换成矩阵乘法就好了。

C语言实现

/**
 * This function is used to initialize the matrix.
 * Make the value of the positive diagonal 1, others 0.
 **/
ll **matrixInit(int n) {
    ll **ans = (ll**) malloc(sizeof(ll*) * n);
    for (int i = 0; i < n; ++i) 
        ans[i] = (ll*) malloc(sizeof(ll) * n);
     for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j)
            ans[i][j] = 0;
        ans[i][i] = 1;
     }
     return ans;
}

ll **matrixMult(ll **x, ll **y, int n) {
    ll **ans = (ll**) malloc(sizeof(ll*) * n);
    for (int i = 0; i < n; ++i) 
        ans[i] = (ll*) malloc(sizeof(ll) * n);
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            ans[i][j] = 0;
    for(int i=0; i < n; ++i)
        for(int k = 0; k < n; ++k) 
            for(int j = 0; j < n; ++j) 
                ans[i][j] = (ans[i][j] + x[i][k] * y[k][j] % MOD) % MOD;
    return ans;
}

/**
 * The method of calculating the nth power of matrix x.
 * The row and column length of matrix X is required to be equal.
 * The incoming parameter is x[ROW][ROW].
 * The result is ans[ROW][ROW].
 **/
ll **matrixPow(ll **x, ll n, int ROW) {
    ll **ans = matrixInit(ROW);
    for (; n; n >>= 1) {
        if(n & 1)
            ans = matrixMult(ans, x, ROW);
        x = matrixMult(x, x, ROW);
    }
    return ans;
}