矩阵快速幂

我们都知道，通过快速幂的算法通过二进制拆分，可以将原本O(n)的复杂度降低到O(logn)

同理，只要一样东西具有像数的乘法一样的运算法则，那也一样可以用快速幂的思路来优化

斐波那契数列

以斐波那契数列为例，我们知道 \( f(n) = f(n-1) + f(n-2) \), 故

\(\left\{\begin{aligned} & f(n) = 1 \times f(n-1) + 1 \times f(n-2) \\ & f(n-1)  = 1 \times f(n-1) + 0 \times f(n-2) \end{aligned}\right.\)

故

\(\begin{bmatrix}f(n)\\ f(n-1)\end{bmatrix}=\begin{bmatrix}1 & 1\\ 1 & 0\end{bmatrix}\times\begin{bmatrix}f(n-1)\\ f(n-2)\end{bmatrix}\)

即

\(\begin{bmatrix}f(n)\\ f(n-1)\end{bmatrix}=\begin{bmatrix}1 & 1\\ 1 & 0\end{bmatrix}^{n-1}\times\begin{bmatrix}1\\ 1\end{bmatrix}\)

然后根据矩阵乘法的公式我们可以写出

struct matrix 
{
    ll dat[2][2] = { {1, 0},
                     {0, 1} };

    matrix operator * (const matrix& b) const
    {
        matrix newMat;
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                newMat.dat[i][j] = 0;
            }
        }
        for (int i = 0; i < 2; i++)
        {
            for (int j = 0; j < 2; j++)
            {
                for (int k = 0; k < 2; k++)
                {
                    newMat.dat[i][j] = newMat.dat[i][j] % mod + dat[i][k] * b.dat[k][j] % mod;
                }
            }
        }
        return newMat;
    }
};

再直接套快速幂的模板即可

template <class T>
T quickPow(T base, ll expo)
{
    T res;
    while (expo > 0)
    {
        if (expo & 1)
        {
            res = res * base;
        }
        base = base * base;
        expo >>= 1;
    }
    return res;
}

拓展一下

增加系数

形如\( f(n) = a \times f(n-1) + b \times f(n-2) \)这样的递推公式

可以得到：

\(\left\{\begin{aligned} & f(n) = a \times f(n-1) + b \times f(n-2) \\ & f(n-1) = 1 \times f(n-1) + 0 \times f(n-2) \end{aligned}\right.\)

即

\(\begin{bmatrix}f(n)\\ f(n-1)\end{bmatrix}=\begin{bmatrix}a & b\\ 1 & 0\end{bmatrix}^{n-1}\times\begin{bmatrix}f(2)\\ f(1)\end{bmatrix}\)

增加常数

形如\( f(n) = f(n-1) + f(n-2) + c \)这样的递推公式

可以得到：

\(\left\{\begin{aligned} & f(n) = 1 \times f(n-1) + 1 \times f(n-2) + c \\ & f(n-1)  = 1 \times f(n-1) + 0 \times f(n-2) + 0  \\ & c = 0 \times f(n-1) + 0 \times f(n-2) + c\end{aligned}\right.\)

即

\(\begin{bmatrix}f(n)\\ f(n-1) \\ c \end{bmatrix}=\begin{bmatrix}1 &  1 & 1 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{bmatrix}^{n-1}\times\begin{bmatrix}f(2)\\ f(1) \\ c \end{bmatrix}\)