矩阵乘法
0111这是一个矩阵，那么我要让它乘以一个这样的矩阵
1001那么它的结果就是
0111如果乘以它自身，那么它的结果就是
1112那么矩阵乘法的公式就应该是
 (此图为网图，侵权可以私信我)
可以发现，矩阵乘法的右单位元应该是
100010001后面的以此类推
因为对于当前行的每一列都会都会乘以一个对应的数，那么当前列要保留的数所对应的位置就应该是 \(1\)，那么经过猜测推算就可以得出上述矩阵。
另外矩阵乘法满足结合律，证明我也不会 (T﹏T)。
矩阵乘法优化递推
斐波那契数列
斐波那契数列你显然可以用 \(O(n)\) 的时间求出来，递推即可。
但是如果 \(n\) 为 \(1e18\) 你就炸开了，所以需要一种方法优化线性的时间复杂度。
由于 \(f_i = f_{i - 1} + f_{i - 2}\) 那么可以变成从 \([f_{i - 2}, f_{i - 1}]\) 到 \([f_{i - 1}, f_{i}]\) 的这样一个过程，我们发现这个其实是个矩阵，其中 \(i\) 是要求和的，而其它的不要保留第一个即可，那么可以由上面讲的矩阵乘法的右单位元和斐波那契数列的递推公式来推出斐波那契数列的这个变化用的矩阵应该是
0111由于下面还要用，所以将该矩阵设为 \(x\)。
所以我们就可以知道 \(f_i\) 怎么求了，那么可以得出任何数的求法，可是还是 \(O(n)\) 的，我们看看式子就明白了怎么做：
\([f_i, f_{i + 1}] = ((([f_1, f_2] \times x) \times x) \times \dots \dots ) \times x\)
由于满足结合律可以拆括号为
\([f_i, f_{i + 1}] = [f_1, f_2] \times x \times x \times \dots \dots \times x\)
还能简化为
\([f_i, f_{i + 1}] = [f_1, f_2] \times x^i\)
那么就很好算了呀，代码如下
[code]#include #include using namespace std;using ll = long long;const int MaxN = 110, mod = 1e9 + 7;struct A { int n, m; ll a[MaxN][MaxN]; A() { fill(a[1], a[MaxN], 0); } void build() { for (int i = 1; i < MaxN; i++) { a = 1; } } void init() { for (int i = 1; i < n && i + 1 |
