目录

了解矩阵的数学原理（大学线性代数）

矩阵及转置矩阵

矩阵乘法 

矩阵快速幂

相伴矩阵模板

[相伴矩阵,快速矩阵幂]CSES1722 Fibonacci Numbers

---

了解矩阵的数学原理（大学线性代数）

矩阵及转置矩阵

 这里A就是一个矩阵，1， 2，3，4就是矩阵里的元素

 就是一个转置矩阵T是转置符 这个矩阵原来是 

矩阵乘法 

  这是矩阵乘法， 矩阵加法和减法简单地定义为逐个元素进行加减。注意，两个矩阵的行数、列数分别相等时，加减法才有定义。矩阵的乘法比较复杂，当A的列数等于B的行数时，则可以定义乘法C=AB。如果A是m×n矩阵，B是n×p矩阵，那么C是一个m×p矩阵，其中cik满足

如果A和B不满足要求的大小就不能够成一个矩阵C。

如果你还理解不了就看一下下面这个线性方程吧

 

 

第一个框是A(矩阵) , 第二个是x(向量， 未知数) 得出的第三个框是b(向量矩阵解)

矩阵乘法是矩阵第一列成第一个未知数

例如：
 

这是我随便写的一个方程， 用矩阵表示为：

大家就知道了第一列表示x在三个方程存在的数量,第二列表示y在三个方程存在的数量, 第三列表示z在三个方程存在的数量。

矩阵快速幂

这是矩阵的关系式：

代码：

// CSES1722 Fibonacci Numbers
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define _for(i, a, b) for (int i = (a); i < (int)(b); ++i)
const LL P = 1e9 + 7;
using VL = vector<LL>;
struct Mat {
  int n, m;
  vector<VL> F;
  Mat(int _n, int _m) : n(_n), m(_m), F(n, VL(m)) {}
  Mat operator*(const Mat& x) const {
    assert(m == x.n);
    Mat ans(n, x.m);
    _for(r, 0, n) _for(c, 0, x.m) {
      _for(i, 0, m)(ans.F[r][c] += F[r][i] * x.F[i][c] % P) %= P;
    }
    return ans;
  }
  Mat operator^(LL k) const {
    assert(k >= 1);
    assert(n == m);
    Mat ans = *this, p = *this;
    for (--k; k; k >>= 1, p = p * p)
      if (k & 1) ans = ans * p;
    return ans;
  }
};
int main() {
  ios::sync_with_stdio(false), cin.tie(0);
  LL n, ans = -1;
  cin >> n;
  if (n == 0)
    ans = 0;
  else if (n == 1)
    ans = 1;
  else {
    Mat A(2, 2), v1(2, 1);
    A.F = {{1, 1}, {1, 0}}, v1.F = {{1}, {0}};
    Mat vn = (A ^ (n - 1)) * (v1);
    ans = vn.F[0][0];
  }
  cout << ans << "\n";
  return 0;
}