矩阵

前置知识

• 定义

基本概念 ： 由 \(n \times m\) 个数排成 \(m\) 行 \(n\) 列的矩形的数表，称为一个 \(m \times n\) 的矩阵，记作 \(A\)。其中 \(a_{i,j}\) 表示第 \(i\) 行第 \(j\) 列的元素。

• 0 矩阵

对于每个矩阵中的元素 \(a_{i,j}\) 都为 0，这个矩阵因此也可表示为 \(0_{n,m}\)

• 单位矩阵

单位矩阵必须保证 \(n = m\)，否则就不是单位矩阵，单位矩阵只有对角线上的数为 1，其余的数都为 0。

举个例子 ：

\[\begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix} \]

这就是个单位矩阵，可以表示为 \(I_{n}\)，单位矩阵的作用相当于我们运算中的 1。用它来乘以任意数都为本身。

• 其他的一些矩阵

好像一般用不到 ？

对角矩阵，纯量矩阵，上三角矩阵，下三角矩阵，对称矩阵，反对称矩阵。

矩阵运算

• 加减法运算

对于相加和相减的两个矩阵，必须保证两个矩阵大小相同才能做矩阵加减法运算。

加减法运算的两个矩阵直接对应位置相加或者相减就可以了。

举个例子 ：

\(\begin{bmatrix} a_{1,1} & \cdots & a_{1,m} \\ \vdots & \ddots & \vdots \\ a_{n,1} & \cdots & a_{n,m} \\ \end{bmatrix}\) + \(\begin{bmatrix} b_{1,1} & \cdots & b_{1,m} \\ \vdots & \ddots & \vdots \\ b_{n,1} & \cdots & b_{n,m} \\ \end{bmatrix}\) = \(\begin{bmatrix} a_{1,1} + b_{1,1} & \cdots & a_{1,m} + b_{1,m} \\ \vdots & \ddots & \vdots \\ a_{n,1} + b_{n,1} & \cdots & a_{n,m} + b_{n,m}\\ \end{bmatrix}\)

是不是很好理解 /cy

矩阵的加减法满足交换律和结合律。

• 数乘运算

\(k \times\) \(\begin{bmatrix} a_{1,1} & \cdots & a_{1,m} \\ \vdots & \ddots & \vdots \\ a_{n,1} & \cdots & a_{n,m} \\ \end{bmatrix}\) = \(\begin{bmatrix} k \times a_{1,1} & \cdots & k \times a_{1,m} \\ \vdots & \ddots & \vdots \\ k \times a_{n,1} & \cdots & k \times a_{n,m} \\ \end{bmatrix}\)

• 矩阵乘法

定义 ： 矩阵的乘法

如果要使用矩阵乘法，两个矩阵必须是其中的一个矩阵的行数等与另一个矩阵的列数，即 \(A_{n,q}\) 与 \(B_{q,m}\) 可以进行矩阵乘法，得出的矩阵的行数是第一个矩阵的行数，矩阵的列数是第二个矩阵的列数。

我们设 \(A = (a_{i,j})_{m \times r},B = (b_{i,j})_{r \times n}\)，则矩阵 \(C = (c_{i,j})_{m,n}\)，其中 \(c_{i,j} = a_{i,1}b_{1,j} + a_{i,2} b_{2,j} + \cdots + a_{i,r} b_{r,j}\)。

记作 \(C = A * B\)。

举个例子 :

我们设一个 \(A_{2,2}\)，一个 \(B_{2,3}\)，我们将会的到一个 \(C_{2,3}\) 的矩阵。

$\begin{bmatrix}
1 & 2 \
3 & 4 \
\end{bmatrix} \times $$\begin{bmatrix}
1 & 2 & 3 \
4 & 5 & 6 \
\end{bmatrix} =$ \(\begin{bmatrix} 9 & 12 & 15 \\ 19 & 26 & 33 \\ \end{bmatrix}\)

\(C_{i,j} = \sum\) 第一个矩阵的第 \(i\) 行的每个数与第二个矩阵的第 \(j\) 列每个数相乘(一一对应)。

矩阵乘法的性质

1. \(0_{n,m} A_{m,k} = 0,A_{k,m} 0_{m,n} = 0\)。
2. \(I_{n,m} A_{m,k} = A,A_{k,m} I_{m,n} = A\)。
3. \(A(BC) = (AB)C\)
4. \(A(B + C) = AB + BC\)，左分配率律
5. \((B + C) A = B A + C A\)，右分配率律

注意左右两分配率矩阵相乘的顺序不能颠倒。

矩阵乘法没有交换律！！！

但是有三种特殊情况，交不交换无所谓。

\(O A = A O = 0\)
\(I A = A I = A\)
\(A A = A A = A ^ 2\)

下面给出一个矩阵乘法的代码。

\(\text{problem}\) ： Link

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int Maxk = 110;
int n,m,p;
struct Matrix {
  int n1,m1;
  int z[Maxk][Maxk];
  Matrix (){
    n1 = m1 = 0;
    memset(z,0,sizeof z);
  }
} A , B ; 
inline int read()
{
	int s = 0, f = 0;char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}
Matrix operator * (const Matrix &m1,const Matrix &m2)
{
  Matrix m3;
  m3.n1 = m1.n1;
  m3.m1 = m2.m1;
  for(int i = 1;i <= m3.n1;i ++) 
    for(int k = 1;k <= m1.m1;k ++) 
      for(int j = 1;j <= m2.m1;j ++)
        m3.z[i][j] += m1.z[i][k] * m2.z[k][j];
  return m3;  
} 
signed main()
{
  n = read(),m = read();
  for(int i = 1;i <= n;i ++) 
    for(int j = 1;j <= m;j ++) 
      A.z[i][j] = read();
  p = read();
  for(int i = 1;i <= m;i ++) 
    for(int j = 1;j <= p;j ++)
      B.z[i][j] = read();
  A.n1 = n,A.m1 = m;
  B.n1 = m,B.m1 = p;
  Matrix Ans = A * B;
  for(int i = 1;i <= n;i ++) {
    for(int j = 1;j <= p;j ++)  {
      cout << Ans.z[i][j] << " ";
    }
    cout << '\n';
  }
  return 0;
}

• 矩阵快速幂

矩阵快速幂就是把快速幂和矩阵乘法结合起来，没有什么很难的，我们只需要像快速幂那样先初始化一个单位矩阵，之后按照快速幂的形式不断相乘即可。

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int mod = 1e9 + 7; 
const int Maxk = 110;
int n,m;
struct Matrix {
  int n1,m1;
  int z[Maxk][Maxk];
  Matrix (){
    n1 = m1 = 0;
    memset(z,0,sizeof z);
  }
} A , E ; 
inline int read()
{
	int s = 0, f = 0;char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}
Matrix operator * (const Matrix &m1,const Matrix &m2)
{
  Matrix m3;
  m3.n1 = m1.n1;
  m3.m1 = m2.m1;
  for(int i = 1;i <= m3.n1;i ++) 
    for(int k = 1;k <= m1.m1;k ++) 
      for(int j = 1;j <= m2.m1;j ++) {
        m3.z[i][j] = m3.z[i][j] + m1.z[i][k] * m2.z[k][j];
        if(m3.z[i][j] >= mod) m3.z[i][j] %= mod;
      }
  return m3;  
} 
signed main()
{
  n = read(),m = read();
  for(int i = 1;i <= n;i ++) 
    for(int j = 1;j <= n;j ++) 
      A.z[i][j] = read();
  A.n1 = n,A.m1 = n;
  for(int i = 1;i <= n;i ++) E.z[i][i] = 1;//初始化单位矩阵
  E.n1 = n,E.m1 = n;
  while(m) {//按照快速幂的方法来乘
    if(m & 1) E = E * A;
    A = A * A;
    m >>= 1; 
  }
  for(int i = 1;i <= n;i ++) {
    for(int j = 1;j <= n;j ++) {
      cout << E.z[i][j] << " ";
    } 
    cout << "\n"; 
  } 
  return 0;
}

矩阵乘法应用 & 矩阵加速

因为矩阵加减法太简单了，所以基本没有什么题目来考矩阵加减法。

斐波那契数列加速求解

\(\text{problem}\) : Link

首先我们知道 \(f_{i} = f_{i - 1} + f_{i - 2}\)。

很多这种递推式都可用矩阵来加速，我们只要找到一个矩阵，保证这个矩阵在不变的情况下就可以来求出下一项，我们就可以矩阵加速求解。

我们定义 \(A\) 矩阵为

\[\begin{bmatrix} f_{n} & f_{n - 1} \end{bmatrix}\]

我们要求的 \(C\) 矩阵为

\[\begin{bmatrix} f_{n + 1} & f_{n} \end{bmatrix}\]

我们要找一个 \(B\) 矩阵，保证在 \(B\) 矩阵不变的情况下就可以进行矩阵加速。

如何来找这个矩阵 ？

首先，我们的 \(C\) 矩阵有一行两列，所以可以得出，我们的 \(B\) 矩阵是两行两列，设 \(B\) 矩阵为 :

\[\begin{bmatrix} a & b \\ c & d \\ \end{bmatrix}\]

根据矩阵乘法，显然可以得到 ：

\[\begin{aligned} f_{n + 1} &= a \times f_{n} + c \times f_{n - 1} \\ f_{n} &= b \times f_n + d \times f_{n - 1} \\ \end{aligned}\]

所以我们很容易的到 \(b = 1,d = 0\)，之后在根据 \(f_n = f_{n - 1} + f_{n - 2}\)，所以 \(a = 1,b = 1\)。

我们的 \(B\) 矩阵就可以得出了 :

\[\begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}\]

之后我们直接套一个快速幂就可以解决了。

#include <cstdio>
#include <cmath>
#include <iostream>
#include <cstring>
#include <algorithm>
#define int long long
using namespace std;
const int mod = 1e9 + 7; 
const int Maxk = 110;
int n,m;
struct Matrix {
  int n1,m1;
  int z[3][3];
  Matrix (){
    n1 = m1 = 0;
    memset(z,0,sizeof z);
  }
} A ,B,E ; 
inline int read()
{
	int s = 0, f = 0;char ch = getchar();
	while (!isdigit(ch)) f |= ch == '-', ch = getchar();
	while (isdigit(ch)) s = s * 10 + (ch ^ 48), ch = getchar();
	return f ? -s : s;
}
Matrix operator * (const Matrix &m1,const Matrix &m2)
{
  Matrix m3;
  m3.n1 = m1.n1;
  m3.m1 = m2.m1;
  for(int i = 1;i <= m3.n1;i ++) 
    for(int k = 1;k <= m1.m1;k ++) 
      for(int j = 1;j <= m2.m1;j ++) {
        m3.z[i][j] = m3.z[i][j] + m1.z[i][k] * m2.z[k][j];
        if(m3.z[i][j] >= mod) m3.z[i][j] %= mod;
      }
  return m3;  
} 
signed main()
{
  n = read();
  if(n == 1 || n == 0) {
    cout << 1 << endl;
    return 0;
  }
  A.z[1][1] = 1,A.z[1][2] = 0;
  A.n1 = 1,A.m1 = 2;
  B.z[1][1] = 1,B.z[1][2] = 1;
  B.z[2][1] = 1,B.z[2][2] = 0;
  B.n1 = 2,B.m1 = 2;
  for(int i = 1;i <= 2;i ++) E.z[i][i] = 1;//初始化单位矩阵
  E.n1 = 2,E.m1 = 2;
  m = n - 1;
  while(m) {
    if(m & 1) E = E * B;
    B = B * B;
    m >>= 1; 
  }
  A = A * E;
  cout << A.z[1][1] % mod;
  return 0;
}

斐波那契数列求和

\(\text{problem}\) : Link

似乎和前面差不多，也是推式子。

我们用 \(S_i\) 代表从第 \(1\) 项到第 \(i\) 项的和，显然 \(A\) 矩阵和 \(C\) 矩阵一样设就行了，上面是 \(A\)，下面是 \(C\)。

\[\begin{bmatrix} f_{n} & f_{n - 1} & S_n \end{bmatrix}\]

\[\begin{bmatrix} f_{n + 1} & f_{n} & S_{n + 1} \end{bmatrix}\]

明显我们要设一个 \(B\) 矩阵，行列都为 3。

\[\begin{bmatrix} a & b & c\\ d & e & f \\ g & h & i \\ \end{bmatrix}\]

得出 ：

\[\begin{aligned} f_{n + 1} &= a \times f_{n} + d \times f_{n - 1} + g \times S_n \\ f_{n} &= b \times f_n + e \times f_{n - 1} + h \times S_n \\ S_{n + 1} &= c \times f_n + f \times f_{n - 1} + i \times S_n \\ \end{aligned}\]

所以化简一下就得到了矩阵 \(B\) ：

\[\begin{bmatrix} 1 & 1 & 1\\ 1 & 0 & 1 \\ 0 & 0 & 1 \\ \end{bmatrix}\]

其实还有一种方法 ：

\[S_n = f_0 + f_1 + \cdots + f_n \\ S_{n + 1} = f_0 + f_1 + \cdots + f_{n + 1} \]

\[\begin{aligned} S_n + S_{n + 1} &= f_0 + f_2 + f_3 + \cdots f_{n + 2} \\ &= S_{n + 2} - f_0 \\ &= S_{n + 2} - 1 \end{aligned}\]

注意如果有常数想的情况下要增加一个维度来存常数项。

\[\begin{bmatrix} S_n & S_{n - 1} & 1 \end{bmatrix}\]

\[\begin{bmatrix} S_{n + 1} & S_{n} & 1 \end{bmatrix}\]

的出的 \(B\) 矩阵为 ：

\[\begin{bmatrix} 1 & 1 & 0\\ 1 & 0 & 0 \\ 1 & 0 & 1 \\ \end{bmatrix}\]

就不再多阐述了。

Problem

由于上课的时候没怎么听懂，先说一下题面。。

Description

\(n\) 个点的图，共有 \(m\) 条边，且都是单向边。

\(M_{i,j}\) 表示从第 \(i\) 个点到第 \(j\) 个点有多少条边。

求从 1 号点走 \(t\) 条边到第 \(n\) 号点的方案数。

\(n \leq 100,t \leq 10 ^ 9\)。

Solution

咕咕咕

如果要用矩阵乘法加速 \(DP\)，要保证两点。

• 必须从 \(i - 1\) 转移到 \(i\)。
• \(M\) 不会随着 \(i\) 的改变而改变，即第二个矩阵无关。