矩阵快速幂

导引问题

快速幂需要long long中间过程

构造矩阵

关键: 构造出k*k的B矩阵！

一、C_n 第1行的 f[n] 与前面的项有什么关系，就在B矩阵的第1行填写对应的系数！

第一行是重点：使用递推公式的系数

在构造矩阵时，C_n 的第二行通常对应 B 矩阵中 f[n-1] 项的系数为 1，其余位置系数为 0。其他列的处理方式类似，按此规则逐列填充即可完成构造。

下面一行靠左写出单位矩阵： 缺项补充0

有常数的特殊情况：

矩阵快速幂的构造-练习2

如果递推公式更复杂一些，你还能构成B矩阵吗？

\[ f(n) = a * f(n-1) + b * f(n-3) + c \]

是不是下面这样的：

\[ \begin{bmatrix} f[n] \\ f[n-1] \\ f[n-2] \\ c \end{bmatrix} = \begin{bmatrix} a & 0 & b & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix} * \begin{bmatrix} f[n-1] \\ f[n-2] \\ f[n-3] \\ c \end{bmatrix} = \begin{bmatrix} a & 0 & b & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}^{n-2} * \begin{bmatrix} f[2] \\ f[1] \\ f[0] \\ c \end{bmatrix} \]

有多次方的特殊情况

矩阵快速幂的构造-练习3

如果递推公式更更更复杂一些，你还能构造成\(\boldsymbol{\mathrm{B}}\)矩阵吗？

\(\boldsymbol{\mathrm{f(1)=1}}\)，\(\boldsymbol{\mathrm{f(2)=2}}\)，\(\boldsymbol{\mathrm{f(n) = f(n−1) + 2f(n−2) + n^3}}\)

特点： 这是一个带变量的递推式！（区别于常量哦~）

难点： 如何在矩阵递推式中构造出\(n^3\)的表达式？

要点： 利用二项式定理得到：

\[n^3 = (n-1+1)^3 = (n-1)^3 + 3(n-1)^2 + 3(n-1) + 1\]

\[\begin{bmatrix} f(n) \\ f(n - 1) \\ n^3 \\ n^2 \\ n \\ 1 \end{bmatrix} = \begin{bmatrix} 1 & 2 & 1 & 3 & 3 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 3 & 3 & 1 \\ 0 & 0 & 0 & 1 & 2 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{bmatrix}^{n-2} \begin{bmatrix} f(2) \\ f(1) \\ 8 \\ 4 \\ 2 \\ 1 \end{bmatrix}\]

区间和

Sn=Sn-1+tn

矩阵快速幂的构造-练习4

如果递推公式更更更更复杂一些，你还能构造成\(\boldsymbol{\mathrm{B}}\)矩阵吗？ \(\mathrm{T}[0]=\mathrm{T}[1]=\mathrm{T}[2]=1\) \(\mathrm{T}[n]=\mathrm{T}[n-1]+\mathrm{T}[n-2]+\mathrm{T}[n-3]\ (n \geq 3)\)

给定\(a\)和\(b\ (1 \leq a \leq b < 10^9)\)，求\((\mathrm{T}[a]+\mathrm{T}[a+1]+\dots+\mathrm{T}[b])\%(10^9+7)\)

要点难点：先求前缀和，然后计算\(\mathrm{S}[b]-\mathrm{S}[a-1]\)，于是问题转化成求\(\mathrm{S}[n]\)

\[ \begin{bmatrix} S[n] \\ T[n] \\ T[n-1] \\ T[n-2] \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} S[n-1] \\ T[n-1] \\ T[n-2] \\ T[n-3] \end{bmatrix} = \begin{bmatrix} 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{bmatrix}^{n-2} \begin{bmatrix} S[2] \\ T[2] \\ T[1] \\ T[0] \end{bmatrix} \]

n取决于分解开需要的项数

平方构造

矩阵快速幂的构造-练习5

如果递推公式更更更更更复杂一些，你还能构造成\(\boldsymbol{B}\)矩阵吗？

\(A(0)=1,A(1)=1,A(n)=X * A(n-1)+Y * A(n-2)\ (n>=2)\)，求\(S(n)=\sum A(i)^2\)

问题分析：因为 \(S(n) = S(n-1) + A(n)^2\)

\[ A(n)^2 = X^2*A(n-1)^2 + 2XY*A(n-1)A(n-2) + Y^2*A(n-2)^2 \]

所以矩阵列向量至少包含\(S(n)\)、\(A(n)^2\)、\(A(n)A(n-1)\)、\(A(n-1)^2\)四项

本题特点：不仅需要前缀和，而且递推表达式更复杂（含乘法项）

\[ \begin{bmatrix} S(n) \\ A(n)^2 \\ A(n)A(n-1) \\ A(n-1)^2 \end{bmatrix} = \begin{bmatrix} 1 & X^2 & 2XY & Y^2 \\ 0 & X^2 & 2XY & Y^2 \\ 0 & X & Y & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix} \begin{bmatrix} S(n-1) \\ A(n-1)^2 \\ A(n-1)A(n-2) \\ A(n-2)^2 \end{bmatrix} = \begin{bmatrix} 1 & X^2 & 2XY & Y^2 \\ 0 & X^2 & 2XY & Y^2 \\ 0 & X & Y & 0 \\ 0 & 1 & 0 & 0 \end{bmatrix}^{n-1} \begin{bmatrix} S(1) \\ A(1)^2 \\ A(1)A(0) \\ A(0)^2 \end{bmatrix} \]

例题 练习6

矩阵快速幂的构造-练习6

一个 01 循环串，长度为L（L<=100），这个串每秒都会进行一次变换，变换规则是：如果左边是1，则改变自己的状态，否则保持不变。

给定初始状态，问 n 秒以后这个串的状态。

问题分析： 定义状态\(f(n,L)\)表示 n 秒以后，第 L 个字符是 0 还是 1；则有如下状态转移方程：

\[ f(n, L) = \begin{cases} f(n - 1, L) & (f(n - 1, L - 1) = 0) \\ 1 - f(n - 1, L) & (f(n - 1, L - 1) = 1) \end{cases} \]

由于\(f(n-1,L)\)的取值只有0和1，所以根据同余的性质可以化简得到：

\[ f(n, L) = f(n-1, L-1) + f(n-1, L) \]

特点难点： 需要构造二维状态的矩阵表达式

构造的矩阵如下：

\[ \begin{bmatrix} f(n, 1) \\ f(n, 2) \\ \vdots \\ f(n, L) \end{bmatrix} = \begin{bmatrix} 1 & 0 & \dots & 0 & 1 \\ 1 & 1 & \dots & 0 & 0 \\ \vdots & \vdots & \dots & 1 & 0 \\ 0 & 0 & \dots & 1 & 1 \end{bmatrix} \begin{bmatrix} f(n-1, 1) \\ f(n-1, 2) \\ \vdots \\ f(n-1, L) \end{bmatrix} \]

总结

在递推式，n很大的时候 6种情况

• 本讲主要介绍了哪几类递推表达式？
• ——普通、含常数、含变量、前缀和、表达式含乘法项、二维状态