矩阵快速幂 笔记

一、简单介绍

一个 $m\times n$ 的矩阵 $A$ 可以和一个 $n\times p$ 的矩阵 $B$ 相乘，得到一个大小为 $n\times p$ 的矩阵 $C$，其中：

$$C_{i,j}=\sum _{k=1}^n{A}_{i,k}\times B_{k,j}$$

那么就可以用快速幂求矩阵幂了。

二、简单应用

1. P1962 斐波那契数列

$f_1=f_2=1$，$f_i=f_{i-1}+f_{i-2}$，求 $f_{n}mod{10}^9+7$。

我们假设矩阵 $\left[\begin{array}{cc}{f}_{i-1}& f_i\end{array}\right]$ 乘上某一个矩阵之后可以得到 $\left[\begin{array}{cc}{f}_i& f_{i+1}\end{array}\right]$，由于 $f_i=0\times f_{i-1}+1\times f_i$，$f_{i+1}=1\times f_{i-1}+1\times f_i$，所以：

$$\left[\begin{array}{cc}{f}_{i-1}& f_i\end{array}\right]\times \left[\begin{array}{cc}0& 1\\ 1& 1\end{array}\right]=\left[\begin{array}{cc}{f}_i& f_{i+1}\end{array}\right]$$

矩阵快速幂解决即可。

2. 数列

$f_1=f_2=0$，$f_i=7\times f_{i-1}+6\times f_{i-2}+4\times 3^i+5\times i$，求 $f_{n}mod{10}^9+7$。

同理，假设矩阵 $\left[\begin{array}{ccccc}{f}_{i-1}& f_i& 4\times 3^i& 5\times i& 5\end{array}\right]$ 乘上某一个矩阵可以得到 $\left[\begin{array}{ccccc}{f}_i& f_{i+1}& 4\times 3^{i+1}& 5\times (i+1)& 5\end{array}\right]$。

由于：

$$\{\begin{array}{ccc}{f}_i& =& 1\times f_i\\ f_{i+1}& =& 6\times f_i+7\times f_{i-1}+3\times 4\times 3^i+1\times 5\times i+1\times 5\\ 4\times 3^{i+1}& =& 3\times 4\times 3^i\\ 5\times (i+1)& =& 1\times 5\times i+1\times 5\\ 5& =& 1\times 5\end{array}$$

所以：

$$\left[\begin{array}{ccccc}{f}_{i-1}& f_i& 4\times 3^i& 5\times i& 5\end{array}\right]\times \left[\begin{array}{ccccc}0& 6& 0& 0& 0\\ 1& 7& 0& 0& 0\\ 0& 3& 3& 0& 0\\ 0& 1& 0& 1& 0\\ 0& 1& 0& 1& 1\end{array}\right]=\left[\begin{array}{ccccc}{f}_i& f_{i+1}& 4\times 3^{i+1}& 5\times (i+1)& 5\end{array}\right]$$

3. CF691E Xor-sequences

给定一个数集 $A$，现在你需要构造一个长度为 $k$ 的序列 $B$，序列 $B$ 的元素从数集 $A$ 中任意挑选，要求 $B$ 中任意相邻的两个数字的异或值二进制表示中 $1$ 的个数是 $3$ 的倍数，求方案数，对 ${10}^9+7$ 取模。

$1\le n\le 100$，$1\le k,a_i\le {10}^{18}$。

设 $f_{i,j}$ 表示当 $B$ 序列长度为 $i$，且最后一个选 $j$ 的方案数，$p(x)$ 表示 $x$ 在二进制下 $1$ 的个数，则：

$$f_{i+1,j}=\sum _{k=1}^n{f}_{i,k}[3\mid p(a_j\oplus a_k)]$$

最终答案即为 $\sum _{i=1}^n{f}_{n,i}$。

考虑优化，由于每一个 $j$ 都只能从固定的某几个 $k$ 转移而来（因为 $a_j\oplus a_k$ 的值与 $i$ 无关），所以考虑矩阵加速。

假设 $\left[\begin{array}{ccccc}{f}_{i,1}& f_{i,2}& f_{i,3}& \dots & f_{i,n}\end{array}\right]$ 乘上某个矩阵可以得到 $\left[\begin{array}{ccccc}{f}_{i+1,1}& f_{i+1,2}& f_{i+1,3}& \dots & f_{i+1,n}\end{array}\right]$，$c(j,k)$ 表示 $3\mid p(a_j\oplus a_k)$。根据上面的状态转移方程，这是一个 $n\times n$ 的矩阵，第 $i$ 行第 $j$ 列的值就是 $c(i,j)$，写个函数即可。

matrix b(n, n, false);
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) b.d[i][j] = check(a[i], a[j]);
b = pow_matrix(b, k - 1);
int ans = 0;
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) ans = (ans + b.d[i][j]) % mod;
cout << ans;

4. P3176 [HAOI2015] 数字串拆分

本文原在 2025-04-07 18:03 发布于本人洛谷博客。

由于 $f(s)$ 的拆分方式不关心顺序，故有 $f(i)=\sum _{j\in [i-m,i)}f(j)$（$f(0)=1$），可理解为在 $f(j)$ 的拆分基础上，添加一个大小为 $(i-j)$ 的数。

那么构造矩阵 $F_i=\left[\begin{array}{ccccc}f(i)& f(i-1)& f(i-2)& \cdots & f(i-m+1)\end{array}\right]$，矩阵快速幂转移即可求出 $f(i)=F_i(1,1)$，假设转移矩阵为 $A$，那么有 $F_i=F_0\times A^i$。

由初中数学知识，$F_{x+y}+F_{z+w}=F_0\times (A^x\times A^y+A^z\times A^w)$，故 $g(s)$ 就相当于将字符串 $s$ 拆成若干段，每一段的转移矩阵相乘，不同拆法的转移矩阵相加。设 $G_i$ 表示 $s$ 前 $i$ 位的转移矩阵，则有转移 $G_i=\sum _{j\in [1,i]}{G}_{j-1}\times A^{s[j:i]}$。

但是 $|s|\le 500$，$A^{s[j:i]}$ 将会涉及指数高精。考虑递推求出所有的 $A^{s[j:i]}$，可以将 $s[j:i]$ 拆位，先求出每个数码的转移矩阵。设 $B_{i,j}=A^{i\times {10}^j}$，递推可求。接着设 $C_{j,i}$ 表示 $s[j:i]$ 的转移矩阵，则有 $C_{j,i}=C_{j+1,i}\times B_{s_j,i-j}$。

最终答案即为 $(F_0\times G_{|s|})(1,1)$。

忽略矩阵乘法，求 $B$ 时间 $O(10\times |s|)$，求 $C$ 时间 $O(|s{|}^2)$，求 $G$ 时间 $O(|s{|}^2)$。瓶颈在求 $C,G$，时间复杂度为 $O(m^3|s{|}^2)$，可以通过。