一些些数学的算法笔记

标签：int 矩阵 cdots 笔记 times 算法 数学 long 乘法

好好好，直接进入正题（

---

首先我们先要讲讲矩阵，矩阵你可以理解成 \(n\times m\) 的一个二维数组，我们如下表示它：

\[\begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,m} \\ a_{2,1} & a_{2,2} & \cdots & a_{2,m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,m} \end{bmatrix} \]

矩阵最重要的一个运算就是矩阵乘法，矩阵乘法就是给定一个 \(n\times m\) 的矩阵 \(A\)，和一个 \(m\times l\) 的矩阵 \(B\)，得到一个 \(n\times l\) 的矩阵 \(C\)，而 \(C\) 的每一位 \(c_{i,j}=\sum_{k=1}^ma_{i,k}\times b_{k,j}\)。简单来说就是 \(c_{i,j}\) 等于 \(A\) 矩阵的第 \(i\) 行，与 \(B\) 矩阵的第 \(j\) 列的元素顺序分别相乘再相加得到的数。

---

矩阵我们一般会把他封装到一个结构体里，接下来看看一道题吧。

LG-P3390 【模板】矩阵快速幂

给定 \(n\times n\) 的矩阵 \(A\)，求 \(A^k\)。

首先我们要声明一件事，矩阵乘法满足结合律，但不满足交换律。前者可以直接爆算得出，后者可以举例得出。我们知道任何满足结合律的运算都可以用快速幂求解，所以我们只要写出矩阵乘法的代码和快速幂的代码即可。

#include <bits/stdc++.h>

using namespace std;

const int kMaxN = 105, kM = 1e9 + 7;

int n;
long long k;

struct M { // 矩阵结构体
  int n, m;
  long long a[kMaxN][kMaxN];
  M(int h, int w) { n = h, m = w, memset(a, 0, sizeof(a)); }
  M() { memset(a, 0, sizeof(a)); } // 这两个都是初始化矩阵
  M operator*(M b) { // 重载乘法运算符，实现矩阵乘法
    M r(n, b.m);
    for (int k = 1; k <= m; k++) {
      for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= b.m; j++) {
          r.a[i][j] = (r.a[i][j] + a[i][k] * b.a[k][j]) % kM;
        }
      }
    }
    return r;
  }
} A;

M fpow(M A, long long b) { // 矩阵快速幂
  M r(n, n);
  for (int i = 1; i <= r.n; i++) {
    r.a[i][i] = 1;
  }
  for (; b; b >>= 1, A = A * A) {
    if (b & 1) r = r * A;
  }
  return r;
}

int main() {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n >> k, A = M(n, n);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cin >> A.a[i][j];
    }
  }
  A = fpow(A, k);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      cout << A.a[i][j] << ' ';
    }
    cout << '\n';
  }
  return 0;
}

介绍完矩阵乘法，你们是不是就要问：“这有什么用呢？”其实这个东西的用处很大，下面再讲一道题。

LG-P1962 斐波那契数列

标签：int,矩阵,cdots,笔记,times,算法,数学,long,乘法
From： https://www.cnblogs.com/lrx-blogs/p/18002279