当前位置：首页 > news >正文

数学知识——矩阵乘法

news 来源：原创 2025/9/18 21:05:24

使用矩阵快速幂优化递推问题

对于一个递推问题，如递推式的每一项系数都为常数，我们可以使用矩阵快速幂来对算法进行优化。
一般形式为：
$F_n=F_1×A^{n-1}$
由于递推式的每一项系数都为常数，因此对于每一步的递推， $A$ 里面都是相同的常数。
对于 $A^{n-1}$ 部分使用快速幂求解，根据 $F_n$ 就能得到最终答案。

矩阵快速幂：

void mul(int c[][N], int a[][N], int b[][N])
{int temp[N][N] = {0};for (int i = 0; i < N; i ++ )for (int j = 0; j < N; j ++ )for (int k = 0; k < N; k ++ )temp[i][j] = (temp[i][j] + (ll)a[i][k] * b[k][j] % m) % m;memcpy(c, temp, sizeof temp);
}
while (k){if (k & 1) mul(f, f, a);mul(a, a, a);k >>= 1;}

斐波那契数列的前n项和

大家都知道 Fibonacci 数列吧， $f_1=1,f_2=1,f_3=2,f_4=3,…,f_n=f_{n−1}+f_{n−2}$ 。
现在问题很简单，输入 $n$ 和 $m$ ，求 $f_n$ 的前 $n$ 项和 $S_n(mod\ m)$ 。

输入格式

共一行，包含两个整数 $n$ 和 $m$ 。

输出格式

输出前 $n$ 项和 $S_n (mod\ m)$ 的值。

数据范围
$1 \leq n \leq 2000000000,$
$1 \leq m \leq 1000000010$

输入样例：

5 1000

输出样例：

我们有递推关系:
$f_n=f_{n-1}+f_{n-2}$
$S_n=S_{n-1}+f_n$
设 $F_n=[f_n,f_{n+1},S_n]$ ，有 $F_n×A=F_{n+1}$ ，根据递推关系求解矩阵 $A$ 。
$[f_n,f_{n+1},S_n]× \begin{bmatrix} a_{11} & a_{12}& a_{13}\\ a_{21}& a_{22}& a_{23}\\ a_{31} & a_{32} & a_{33} \end{bmatrix}=[f_{n+1},f_{n+2},S_{n+1}]$

求解得到 $\begin{bmatrix} 0 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 0 & 1 \end{bmatrix}$

$F_1=[1,1,1]$ ，最终答案为 $F_1×A^{n-1}$ ，对于 $A^{n-1}$ 部分采用快速幂来计算，时间复杂度为 $O(logn*3^3)$ 。

佳佳的斐波那契

佳佳对数学，尤其对数列十分感兴趣。

在研究完 Fibonacci 数列后，他创造出许多稀奇古怪的数列。

例如用 $S (n)$ 表示 Fibonacci 前 $n$ 项和 $mod\ m$ 的值，即 $S(n)=(F_1+F_2+…+F_n)mod\ m$ ，其中 $F_1=F_2=1,F_i=F_{i−1}+F_{i−2}$ 。

可这对佳佳来说还是小菜一碟。

终于，她找到了一个自己解决不了的问题。

用 $T(n)=(F_1+2F_2+3F_3+…+nF_n)mod\ m$ 表示 Fibonacci 数列前 $n$ 项变形后的和 $mod\ m$ 的值。

现在佳佳告诉你了一个 $n$ 和 $m$ ，请求出 $T (n)$ 的值。

输入格式

共一行，包含两个整数 $n$ 和 $m$ 。

输出格式

共一行，输出 $T (n)$ 的值。

数据范围
$1≤n,m≤2^{31−1}$

输入样例：

5 5

输出样例：

样例解释
$T(5)=(1+2×1+3×2+4×3+5×5)mod\ 5=1$

我们有递推关系:
$f_n=f_{n-1}+f_{n-2}$
$S_n=S_{n-1}+f_n$
$T_n=T_{n-1}+n*f_n$
但是对于 $T_n=T_{n-1}+n*f_n$ ， $f_n$ 的系数不为常数，所以无所用矩阵快速幂来优化。

令 $P_n=nS_n-T_n$ ,那么有：
$P_n=(n-1)S_1+(n-2)S_2...+S_{n-1}$ ,
$P_{n+1}=nS_1+(n-1)S_2...+2S_{n-1}+S_{n}$ ,
$P_{n+1}-P_n=S_n$
于是，我们有以下三组递推关系：
$f_n=f_{n-1}+f_{n-2}$
$S_n=S_{n-1}+f_n$
$P_n=P_{n-1}+S_{n-1}$
每一组的系数都为常数，我们可以使用矩阵快速幂来优化。
设 $F_n=[f_n,f_{n+1},S_n,P_n]$ ，有 $F_n×A=F_{n+1}$ ，根据递推关系求解矩阵 $A$ 。
$[f_n,f_{n+1},S_n,P_n]× \begin{bmatrix} a_{11} & a_{12}& a_{13}& a_{14}\\ a_{21}& a_{22}& a_{23}& a_{24}\\ a_{31} & a_{32} & a_{33}& a_{34}\\ a_{41} & a_{42} & a_{43}& a_{44}\\ \end{bmatrix}=[f_{n+1},f_{n+2},S_{n+1},P_{n+1}]$
根据递推关系，解出
$\begin{bmatrix} 0 & 1 & 0 & 0\\ 1 & 1 & 1 & 0\\ 0 & 0 & 1 & 1\\ 0 & 0 & 0 & 1 \end{bmatrix}$
$F_1=[1,1,1,0],$ $F_n=F_1×A^{n-1}$
解出来 $S_n$ 和 $P_n$ ，最终答案 $T_n=nS_n-P_n$ 。
时间复杂度为 $O(logn*4^3)$ 。

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 4;
int n, m;
void mul(int a[][N], int b[][N], int c[][N])
{int temp[N][N] = {0};for (int i = 0; i < N; i ++ )for (int j = 0; j < N; j ++ )for (int k = 0; k < N; k ++ )temp[i][j] = (temp[i][j] + (ll)b[i][k] * c[k][j] % m) % m;memcpy(a, temp, sizeof temp);
}
int main()
{cin >> n >> m;int f[N][N] = {1, 1, 1, 0};int a[N][N] = {{0, 1, 0, 0},{1, 1, 1, 0},{0, 0, 1, 1},{0, 0, 0, 1}};int k = n - 1;while (k){if (k & 1) mul(f, f, a);mul(a, a, a);k >>= 1;}cout << ((ll)n * f[0][2]% m - f[0][3] + m) % m << endl;return 0;
}

使用矩阵快速幂优化递推问题

斐波那契数列的前n项和

佳佳的斐波那契

相关文章：