The solution of「P1962」 | 矩阵快速幂学习笔记

· · 题解

\textup{Part 0.} 前言

\textup{Link.}

偶然间和朋友讨论斐波那契通项公式发现这题还可以写题解，于是发一篇好久以前的学习笔记作为题解。

\textup{Part 1.} 矩阵乘法

顺便提一嘴，矩阵加法、减法为两个矩阵每一位做运算，注意需要两个矩阵行列相同。

矩阵乘法，顾名思义，将两个矩阵相乘的意思，但与一般的乘法定义不同。

假定有矩阵 A 大小为 a \times m 和 B 大小为 m \times b。

则相乘可以得到大小为 a \times b 的矩阵 C。

注意此处行列对应。

给出公式 C_{i,j} = \sum^m_{k = 1} A_{i,k} \times B_{k, j}。

用人话说就是 C_{i, j} 为 A 的第 i 行与 B 的第 j 列的积。

矩阵乘法具有结合律，可以自行证明。

该运算单位元大致长这样：

\begin{bmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{bmatrix}

其实就是对角线为 1，证明略。

此处单位元指的是一个矩阵乘上这个矩阵也不会改变其的值。

即 x \cdot y = x 时的 y。

:::success[\textup{Code}]

struct matrix{
    int a[MAXN][MAXN];
    matrix operator * ( const matrix & b ) const {
        matrix ans;
        for( int i = 1; i <= N; i ++ )
            for( int j = 1; j <= N; j ++ ){
                ans.a[i][j] = 0;
                for( int r = 1; r <= N; r ++ )
                    ans.a[i][j] = ( (long long) a[i][r] * b.a[r][j] % MOD + ans.a[i][j] % MOD ) % MOD;
            }
        return ans;
    }
}a;

:::

\textup{Part 2.} 矩阵快速幂

与普通数值之间的乘法类似的，矩阵可以用快速幂加速。

至于为什么可以，请看。

:::info[广义上的快速幂要满足以下几个条件]

于是实现只需要在我们上文的板子上加上快速幂即可，如下。

:::success[\textup{Code}]

struct matrix{
    int a[MAXN][MAXN];

    void unit(){//注：此处是初始化单位元
        for( int i = 1; i <= N; i ++ )
            for( int j = 1; j <= N; j ++ )
                a[i][j] = ( i == j );
    }

    matrix operator * ( const matrix & b ) const {
        matrix ans;
        for( int i = 1; i <= N; i ++ )
            for( int j = 1; j <= N; j ++ ){
                ans.a[i][j] = 0;
                for( int r = 1; r <= N; r ++ )
                    ans.a[i][j] = ( (long long) a[i][r] * b.a[r][j] % MOD + ans.a[i][j] % MOD ) % MOD;
            }
        return ans;
    }
    matrix qmpow( int x ){//快速幂
        matrix ans, base;
        ans.init();
        base = *this;
        while( x ){
            if( x & 1 ) ans = ans * base;
            base = base * base;
            x >>= 1;
        }
        return ans;
    }
}a;

:::

\textup{Part 3. Fibonacci}

考虑到 O(N) 递推过于劣，所以使用矩阵快速幂进行加速。

定义某状态下矩阵为:

\begin{bmatrix} f_i \\ f_{i - 1} \end{bmatrix}

此处 f_i 与斐波那契 O(N) 做法时相同的，不加赘述。

一般转移即为 f_i = f_{i - 1} + f_{i - 2}。

那么通过上文乘法的定义可以得到转移矩阵：

\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \cdot \begin{bmatrix} f_{i - 1} \\ f_{i - 2} \end{bmatrix}

可以对这个式子进行快速幂算出答案，便做完了。

:::success[\textup{Code}]

这个是我还没有写封装之前写的，将就着看吧。

const int MAXN = 3;
int N, k, p;
int T;
struct matrix{
    int a[MAXN][MAXN];
    void init(){
        a[1][1] = a[1][2] = a[2][1] = 1;
        a[2][2] = 0;
    }
    void unit(){
        a[1][1] = 1; a[1][2] = 0;
        a[2][1] = 0; a[2][2] = 1;
    }
    matrix operator * ( const matrix & b ){
        matrix ans;
        for( int i = 1; i <= 2; i ++ )
            for( int j = 1; j <= 2; j ++ ){
                ans.a[i][j] = 0;
                for( int r = 1; r <= 2; r ++ )
                    ans.a[i][j] = ( (long long) a[i][r] * b.a[r][j] % p + ans.a[i][j] % p ) % p;
            }
        return ans;
    }
};

int mqpow( int x ){
    matrix ans, base;
    ans.unit(), base.init();
    while( x ){
        if( x & 1 ) ans = ans * base;
        base = base * base;
        x >>= 1;
    }
    return ans.a[1][1];
}
signed main(){
    IOS;
    T = 1;
    while( T -- ){
        int kkks;
        cin >> kkks;
        p = 1e9 + 7;
        if( kkks == 0 || kkks == 1 ) cout << 1 << endl;
        else cout << mqpow( kkks - 1 ) << endl;
    }
    return 0;
}

:::

\textup{Part 4.} 一些推广

如何将这个问题推广下去？

这里有几种问题：

一般来说，在矩阵中添加所需的量并且推出转移矩阵即可。

一点练习：

1 | 2 | 3 | 4

:::info[\textup{Last}]

审核管理员辛苦了，如果您有什么看不懂、我太弱了所以讲错了的地方，请您在评论区指出或找我，我会一定解答并且修改本题解。

如果您觉得本文写的还不错，那可以留个赞吗?

QWQ。

谢谢你看到这里~ :::