目录
[相伴矩阵,快速矩阵幂]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在三个方程存在的数量。
矩阵快速幂
这3个矩阵分别为A, x和b（注意x和b都是n×1的矩阵，也称列向量），则线性方程组可以简单地写成Ax=b。这样是不是很方便呢？建议读者仔细研究一下这个Ax=b。它意味着A把一个列向量x变成了另外一个列向量b。也就是说，矩阵A描述的是一个线性变换，它把向量x变换到了向量b。在算法竞赛中，只要遇到“把一个向量v变成另一个向量v'，并且v' 的每一个分量都是v各个分量的线性组合”的情况，就可以考虑用矩阵乘法来描述这个关系。这里的线性组合是指每个元素乘以一个常数后相加。比如2x+3y-z就是x、y、z的线性组合，但5xy和x2-3y都不是。矩阵乘法最重要的性质就是满足结合律，即(AB)C=A(BC)，因此和幂取模一样，An也可以用倍增法加速。
摘自： 202403-榕阳-提高组-专题基础-P05-矩阵计算 (kdocs.cn)
https://www.kdocs.cn/l/cqHzHcSMgykl
相伴矩阵模板
[相伴矩阵,快速矩阵幂]CSES1722 Fibonacci Numbers
定义Fibonacci 如下：F0=1,F1=1,Fn=Fn-2+Fn-1。对于指定的n(0≤n≤10^18)，计算斐波那契数列第n项的值，结果对10^9+7取模。
样例输入： |
样例输出： |
10 |
55 |
这是矩阵的关系式：
代码：
// 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;
}