矩阵乘法与优化
矩阵乘法
| 0 | 1 |
|---|---|
| 1 | 1 |
这是一个矩阵，那么我要让它乘以一个这样的矩阵
| 1 | 0 |
|---|---|
| 0 | 1 |
那么它的结果就是
| 0 | 1 |
|---|---|
| 1 | 1 |
如果乘以它自身，那么它的结果就是
| 1 | 1 |
|---|---|
| 1 | 2 |
那么矩阵乘法的公式就应该是
可以发现，矩阵乘法的左单位元应该是
| 1 | 0 | 0 |
|---|---|---|
| 0 | 1 | 0 |
| 0 | 0 | 1 |
后面的以此类推
因为对于当前行的每一列都会都会乘以一个对应的数，那么当前列要保留的数所对应的位置就应该是 \(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\) 是要求和的，而其它的不要保留第一个即可，那么可以由上面讲的矩阵乘法的左单位元来推出斐波那契数列的这个变化用的矩阵应该是
| 0 | 1 |
|---|---|
| 1 | 1 |
由于下面还要用，所以将该矩阵设为 \(x\)。
所以我们就可以知道 \(f_i\) 怎么求了，那么可以得出任何数的求法，可是还是 \(O(n)\) 的，我们看看式子就明白了怎么做：
\([f_i, f_{i + 1}] = x \times \dots \dots (x \times (x \times [f_1, f_2]))\)
由于满足结合律可以简化为
\([f_i, f_{i + 1}] = x \times x \times \dots \dots \times x \times [f_1, f_2]\)
还能简化为
\([f_i, f_{i + 1}] = x^i \times [f_1, f_2]\)
那么就很好算了呀，代码如下
#include <algorithm>
#include <iostream>
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[i][i] = 1;
}
}
void init() {
for (int i = 1; i < n && i + 1 <= m; i++) {
a[i + 1][i] = 1;
}
for (int i = 1; i <= n; i++) {
a[i][m] = 1;
}
}
A operator*(const A &b) const {
A c;
c.n = n, c.m = b.m;
for (int i = 1; i <= n; i++) {
for (int k = 1; k <= m; k++) {
for (int j = 1; j <= b.m; j++) {
c.a[i][j] = (c.a[i][j] + a[i][k] * b.a[k][j] % mod) % mod;
}
}
}
return c;
}
} a, c;
ll n, m;
A qpow(A a, ll b) {
A res;
res.build(), res.n = a.n, res.m = a.m;
for (ll i = 1; i <= b; i <<= 1) {
if (b & i) {
res = res * a;
}
a = a * a;
}
return res;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n;
a.n = 2, a.m = 1, a.init();
c.n = c.m = 2, c.init();
c = qpow(c, n), a = c * a;
cout << a.a[1][1] << '\n';
return 0;
}
未完待续……