## 矩陣乘法 |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}] = ((([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\)
那麼就很好算了呀，代碼如下
#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 < 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 = 2;
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 = 1, a.m = m;
a.a[a.n][a.m] = 1;
c.n = c.m = m, c.init();
c = qpow(c, n), a = a * c;
cout << a.a[1][m] << '\n';
return 0;
}
那麼如果是 \(f_i = f_{i - 1} + f_{i - 2} + \dots \dots + f_{i - m}\) 呢
那麼我們其實可以理解為斐波那契數列的擴展，那麼同樣的我們可以得到變化是要乘的矩陣應該是，對於每個 \(i\) 其 \([i + 1, i]\) 為一，且第 \(m\) 列全為 \(1\)。
代碼如下
#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 < 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 >> m;
a.n = 1, a.m = m;
a.a[a.n][a.m] = 1;
c.n = c.m = m, c.init();
c = qpow(c, n), a = a * c;
cout << a.a[1][m] << '\n';
return 0;
}
未完待續……
