矩阵&矩阵加速学习笔记

XiaoYao789 · 2025-07-17 12:54:17 · 算法·理论

什么是矩阵：

简单来说，矩阵是一个按照矩形排列的数表，由行（\text{row}）和列（\text{column}）组成，用于表示数据、方程、线性变换等。

常见类型的矩阵：

• 方阵：行数等于列数（n = m）。

• 行向量：只有一行的矩阵（1\times m）。

• 列向量：只有一列的矩阵（n \times 1）。

• 零矩阵：所有元素均为 0。

• 单位矩阵（I）：方阵，主对角线元素为 1，其余为 0。例子：

  I =\begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix} $。

矩阵的常见操作：

• 加法/减法：同维度的矩阵对应元素相加/减。代码：

const int N=5;
void add(int a[][N],int b[][N],int c[][N]){
//矩阵a和b进行加法,结果保留在c中
  static int t[N][N];
  memset(t,0,sizeof t);
  for(int i=1;i<N;i++){
    for(int j=1;j<N;j++){
      t[i][j]+=a[i][j]+b[i][j];
    }
  }
  memcpy(c,t,sizeof t);
}

• 数乘：矩阵每个元素乘以一个标量。

• 转置（A ^ {T}）：行列互换。代码：

const int N=5;
void zhuan_zhi(int a[][N],int b[][N]){
//矩阵a进行转制,结果保留在b中
  static int t[N][N];
  memset(t,0,sizeof t);
  for(int i=1;i<N;i++){
    for(int j=1;j<N;j++){
      t[j][i]=a[i][j];
    }
  }
  memcpy(b,t,sizeof t);
}

• 逆矩阵（A ^ {−1} ）：仅方阵可能存在时，满足 AA ^ {-1} = I。

• 矩阵乘法：若 A 是 n \times m 的矩阵，B 是 m \times k 矩阵，则乘积 AB 是 n \times k 矩阵（不满足交换律）。代码：

  const int N=5;
  void mul(int a[][N],int b[][N],int c[][N]){
  //矩阵a和b进行乘法(a*b),结果保留在c中
  static int t[N][N];
  memset(t,0,sizeof t);
  for(int i=1;i<N;i++){
    for(int j=1;j<N;j++){
      for(int k=1;k<N;k++){
        t[i][j]+=a[i][k]*b[k][j];
      }
    }
  }
  memcpy(c,t,sizeof t);
  }

::::info[矩阵乘法过程模拟]{open} ::::

有的人可能就会问了，作者作者，矩阵在 \texttt{C++} 中也没有啥用啊，让我白看这么久。

其实，你说错了，有一个黑科技，他就是矩阵加速！让算法飞起来的数学魔法！

矩阵加速的定义

矩阵加速是一种利用矩阵快速幂来优化线性递推问题时间复杂度的重要方法，能将许多 O(n) 时间复杂度的递推问题优化到 O(\log n)。

转移矩阵的构建

基本原理

对于形如 f(n) = a_1 \cdot f(n-1) + a_2 \cdot f(n-2) + ... + a_k \cdot f(n-k) 的线性递推关系，我们可以将其转化为矩阵幂运算的形式：

::::success[解释] 对于第一行，f(n) = a_1 \times f(n-1) + a_2 \times f(n-2) + \cdots + a_k \times f(n-k)。

示例（斐波那契数列）：

第一行：f(n) = 1*f(n-1) + 1*f(n-2)。

第二行：保持 f(n-1)。

结果矩阵的初始化：

1. 单位矩阵：

   • 对角线为 1，其余为 0。

2. 初始状态向量：

   • 包含已知的前 k 项值。

例题讲解

P1939

转移矩阵

首先明确想要的矩阵，

和转移过来的矩阵，

构建式子

根据 f(n)=f(n-1)+f(n-3)，解出 A=1,B=0,C=1。

其余的根据 f(i)=f(i) 解出 D=1,E=0,F=0,G=0,H=1,I=0。然后转移矩阵就构建好了。

初始矩阵

因为

所以初始矩阵为 \begin{bmatrix} f(3) \\ f(2) \\ f(1) \\ \end{bmatrix}。

代码点这。

::::warning[注意] 矩阵乘的时候矩阵的顺序别填反了。 ::::

::::success[题单链接] https://www.luogu.com.cn/training/1074066 ::::