目录

对矩阵和矩阵快速幂的讲解

前置知识

对整数快速幂，这里只做个简要介绍：

如果我让你算 $11^4$，你会怎么做？肯定不是把 $11$ 连乘 $4$ 次吧。大多数人会把 $11$ 先平方一次，然后再平方。那如果是 $11^5$ 呢？当然是先用上述方法求出 $11^4$，再乘 $11$。如果是 $11^6$ 呢？这时候，你应该不会用 $11^4$ 去乘两次 $11$。在算 $11^4$ 时，我们已经算出了 $11^2$（第一次平方那里），所以，我们可以用 $11^4$ 乘 $11^2$。综上所述，整数快速幂就是将形如 $a^{2^n}(n\in \mathbb{N})$ 的数乘起来，得到 $a^b$；其中的 $a^{2^n}$ 可以由 $a$ 平方得来。而其中把 $b$ 拆成 $2^n$ 的和的形式可以看成把 $b$ 转化成二进制，进而可以用 按位取出 的方法实现。

代码：

int fastpow(int a,int b,int mod) //求 a^b%mod 的值
{
    int ans=1;
    for( ;b;b>>=1) //n>>=1相当于n/=2
    {
        if(b&1) ans=(ans*a)%mod;
        a=(a*a)%mod;
    }
    return ans;
}

矩阵乘法：

设 $A$ 为 $m \times p$ 的矩阵，$B$ 为 $p \times n$ 的矩阵，那么称 $m \times n$ 的矩阵 $C$ 为矩阵 $A$ 与 $B$ 的乘积，记作 $C=AB$，其中矩阵 $C$ 中的第 $i$ 行第 $j$ 列元素可以表示为：
$C_{ij}= \sum\limits_{k=1}^{p} a_{ik} \times b_{kj}=a_{i1} \times b_{1j}+a_{i2} \times b_{2j}+ \dots +a_{ip} \times b_{pj}$

代码：

matrix operator * (matrix a,matrix b) //a是m*p的矩阵，b是p*n的矩阵
{
    matrix ans={};
    for(int i=0;i<=m;i++)
    {
        for(int k=0;k<=p;k++)
        {
            if(!a[i][k]) continue; //对稀疏矩阵很有用
            for(int j=0;j<=n;j++)
            {
                ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j]);
            }
        }
    }
    return ans;
}

需要的性质：

乘法结合律：$(AB)C=A(BC)$
单位矩阵：$AE=EA=A$，其中的单位矩阵 $E$ 符合：行数等于列数，对角线上的元素都是 $1$，其余都是 $0$。

• 更多矩阵知识，请看 百度百科 。

例题

求斐波那契数列的第 $n$ 项（此处斐波那契数列从一个1开始）。

思路

首先，让我们构造一个 答案矩阵：
$$ F(n)= \begin{pmatrix} f(n) & f(n-1) \end{pmatrix} $$
其次，我们还需要一个 转移矩阵：
$$base= \begin{pmatrix} 1 & 1 & \\ 1 & 0 \end{pmatrix} $$
使得：
$$F(n)=F(n-1) \times base$$
为什么这个 $base$ 矩阵可以实现上面的转移呢？因为：
$$ F(n-1)\times base $$$$ = \begin{pmatrix} f(n-1) & f(n-2) \end{pmatrix} \times \begin{pmatrix} 1 & 1 & \\ 1 & 0 \end{pmatrix} $$$$ = \begin{pmatrix} f(n-1)\times 1+f(n-2)\times 1 & f(n-1)\times 1 \end{pmatrix} $$$$ = \begin{pmatrix} f(n-1)+f(n-2) & f(n-1) \end{pmatrix} $$$$ = \begin{pmatrix} f(n) & f(n-1) \end{pmatrix} $$$$ =F(n) $$
又因为矩阵乘法有结合律，所以
$$ F(n) \\ =F(1)\times base^{n-1} \\ = \begin{pmatrix} 1 & 0 \end{pmatrix} \times \begin{pmatrix} 1 & 1 & \\ 1 & 0 \end{pmatrix}^{n-1} $$
这就是矩阵快速幂的原理。

Code

# include <bits/stdc++.h>
using namespace std;


const int mod=10000;
int n;
struct matrix //用结构体定义矩阵
{
    int m[2][2];
};


matrix operator * (matrix a,matrix b) //重载矩阵乘法
{
    matrix ans={};
    for(int i=0;i<=1;i++)
    {
        for(int k=0;k<=1;k++)
        {
            for(int j=0;j<=1;j++)
            {
                ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%mod;
                //思考：为什么在计算矩阵乘法时可以对每一项取模？
            }
        }
    }
    return ans;
}


int fastpow(int n)
{
    matrix ans={1,0,0,1},base={1,1,1,0};
    for( ;n;n>>=1)
    {
        if(n&1) ans=ans*base;
        base=base*base;
    }
    return ans.m[1][0];
}


int main()
{
    while(true)
    {
        cin>>n;
        if(!~n) break; //判断是否结束输入
        cout<<fastpow(n)<<'\n';
    }
    return 0;
}

思考题

使用 快速幂优化 计算以下数列第 $n$ 项 $\bmod 10^9+7$ 的值：
1. $a_n=a_{n-1}+2a_{n-2}\quad (a_1=0,a_2=1)$
2. $a_n=3a_{n-1}-2a_{n-2}+1\quad (a_1=0,a_2=1)$
3. $a_n=\Sigma_{i=1}^{n-1}[(n-i)\times a_i] \quad (a_1=1)$
4. $a_n=a_{n-1}\times a_{n-2}\quad (a_1=2,a_2=3)$