AI 助理
备案控制台
开发者社区 云计算 文章 正文

【矩阵快速幂 | 斐波那契数列 | 矩阵加速】

2023-05-20 128
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 笔记

基础知识

1. 矩阵结构

struct Matrix {
    int g[N][N];
        // 矩阵初始化。type 为 true 则初始化为 E，type 为 false 则初始化为 O。
    void init(bool type) {
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= n; j++) 
                if(i != j) g[i][j] = 0;
                else g[i][j] = type == true ? 1 : 0;
    }
};

2. 重载 * 运算符

Matrix operator*(const Matrix &o) const {
    Matrix t;
    t.init(false); // 0 矩阵
    for (int i = 1; i <= n; i++) // 三重循环
        for (int j = 1; j <= n; j++) 
            for (int k = 1; k <= n; k++)
                t.g[i][j] = (t.g[i][j] + o.g[i][k] * g[k][j]) % mod;
    return t;
}

3. 矩阵快速幂

// 计算a^k
Matrix operator^(Matrix a, int k) { // 重载矩阵快速幂
    Matrix res;
    res.init(true); 
    while (k) {
        if (k & 1) res = res * a;
        a = a * a;
        k >>= 1;
    }
    return res;
}

例题1： 矩阵幂求和

矩阵幂求和40.png

代码如下：

#include <iostream>
using namespace std;
// https://www.acwing.com/solution/content/15850/
typedef long long ll;
const int N = 110;
int n, mod, k;
// const int mod = 1e9 + 7;
struct Matrix {
    int g[N][N];
    // 矩阵初始化。type 为 true 则初始化为 E，type 为 false 则初始化为 O。
    void init(bool type) {
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= n; j++) 
                if(i != j) g[i][j] = 0;                 // 两种矩阵的共同点：不在 i = j 对角线上的数皆为 0
                else g[i][j] = type == true ? 1 : 0;    // 不同点：在 i = j 对角线上，E 为 1，O 为 0
    }
    Matrix operator*(const Matrix &o) const {
        Matrix t;
        t.init(false);
        for (int i = 1; i <= n; i++) 
            for (int j = 1; j <= n; j++) 
                for (int k = 1; k <= n; k++)
                    t.g[i][j] = (t.g[i][j] + o.g[i][k] * g[k][j]) % mod;
        return t;
    }
    Matrix operator+(const Matrix &o) const // 重载矩阵加法
    {
        Matrix t;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                t.g[i][j] = (g[i][j] + o.g[i][j]) % mod;
        return t;
    }
    void print() {  // 将该矩阵输出
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= n; j++)
                printf("%d ", g[i][j]);
            puts("");
        }
    }
    void read() { // 读入该矩阵
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++) {
                scanf("%d", &g[i][j]);
                g[i][j] %= mod;
            }
    }
};
// 计算a^k
Matrix operator^(Matrix a, int k) { // 重载矩阵快速幂。由于要用到乘法，所以在结构体外重载。
    Matrix res;
    res.init(true); 
    while (k) {
        if (k & 1) res = res * a;
        a = a * a;
        k >>= 1;
    }
    return res;
}
Matrix E, v; // E 即 E 矩阵，v 为读入矩阵
// 计算S=A+A**2+A**3+...+A**k
Matrix S(int k) {
    if (k == 1) return v;                  // 如果 k 为 1，那么返回 v，终止递归。
    if (k & 1) return v + v * S(k - 1);    // 如果 k 是奇数，那么返回上述 A + A * S(k - 1)
    return (E + (v ^ k >> 1)) * S(k >> 1); // 否则返回上述 (E + A ^ (k / 2)) * S(k / 2)
}
int main() {
    cin >> n >> k >> mod;       // scanf
    E.init(true);   // 初始化矩阵E
    v.read();       // 读入矩阵v
    S(k).print();   // 计算S(k)并输出
    return 0;
}

例题2： 矩阵快速幂

矩阵快速幂

  • 框架如上题，PS： long long
scanf("%lld %lld", &n, &k);
    E.init(true);
    v.read();
    (v^k).print();
• 1
• 2
• 3
• 4


例题3： 斐波那契数列

50.png

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 3;
struct Matrix {
    ll g[N][N];
};
Matrix E, v; // E是单位阵（也是最终答案矩阵（快速幂））， v是推导出的初始的2×2 矩阵
void init() {
    memset(E.g, 0, sizeof(E));
    for (int i = 1; i <= 2; i++) E.g[i][i] = 1;
    memset(v.g, 0, sizeof(v.g));
    v.g[1][1] = v.g[1][2] = v.g[2][1] = 1;
}
Matrix mul(Matrix a, Matrix b) {
    Matrix t;
    memset(t.g, 0, sizeof(t));
    for (int i = 1; i <= 2; i++) 
        for (int j = 1; j <= 2; j++)
            for (int k = 1; k <= 2; k++)
                t.g[i][j] = (t.g[i][j] + a.g[i][k] * b.g[k][j]) % mod;
    return t;
}
void qmi(ll k) {
    while(k) {
        if(k & 1) E = mul(E, v);
        v = mul(v, v);
        k >>= 1;
    }
}
void print(Matrix a) {
    for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= 2; j++)
            cout << a.g[i][j] << " ";
        cout << endl;
    }
}
int main() {
    ll n; cin >> n;
    init();
    qmi(n - 1);
    cout << E.g[1][1] << endl;
    return 0;
}

例题4： 矩阵加速

矩阵加速

#include <iostream>
#include <cstring>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 4;
int T, n;
struct Matrix {
    ll g[N][N];
};
Matrix E, v;
void init() {
    memset(E.g, 0, sizeof(E.g));
    for (int i = 1; i <= 3; i++) E.g[i][i] = 1;
    memset(v.g, 0, sizeof(v.g));
    v.g[1][1] = v.g[1][3] = v.g[2][1] = v.g[3][2] = 1;
}
Matrix mul(Matrix a, Matrix b) {
    Matrix t;
    memset(t.g, 0, sizeof(t.g));
    for (int i = 1; i <= 3; i++) 
        for (int j = 1; j <= 3; j++)
            for (int k = 1; k <= 3; k++)
                t.g[i][j] = (t.g[i][j] + a.g[i][k] * b.g[k][j]) % mod;
    return t;
}
void qmi(int k) {
    init();
    while(k) {
        if(k & 1) E = mul(E, v);
        v = mul(v, v);
        k >>= 1;
    }
}
void print(Matrix a) {
    for (int i = 1; i <= 3; i++) {
        for (int j = 1; j <= 3; j++)
            cout << a.g[i][j] << " ";
        cout << endl;
    }
}
int main() {
    cin >> T;
    while(T--) {
        cin >> n;
        if(n <= 3) {
            cout << 1 << endl;
            continue;
        }
        qmi(n);
        cout << E.g[2][1] << endl;
    }
    return 0;
}

例题5： 广义斐波那契

广义斐波那契

60.png

void init() {
    memset(E.g, 0, sizeof(E.g));
    E.g[1][1] = a2, E.g[1][2] = a1;
    memset(v.g, 0, sizeof(v.g));
    v.g[1][1] = p;
    v.g[1][2] = 1;
    v.g[2][1] = q;
}

例题6： 斐波那契公约数

斐波那契公约数


结论：g c d ( F n ,   F m ) = F ( g c d ( n ,   m ) )

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int mod = 1e8;
const int N = 3;
struct Matrix {
    ll g[N][N];
};
Matrix E, v; // E是单位阵（也是最终答案矩阵（快速幂））， v是推导出的初始的2×2 矩阵
void init() {
    memset(E.g, 0, sizeof(E));
    for (int i = 1; i <= 2; i++) E.g[i][i] = 1;
    memset(v.g, 0, sizeof(v.g));
    v.g[1][1] = v.g[1][2] = v.g[2][1] = 1;
}
Matrix mul(Matrix a, Matrix b) {
    Matrix t;
    memset(t.g, 0, sizeof(t));
    for (int i = 1; i <= 2; i++) 
        for (int j = 1; j <= 2; j++)
            for (int k = 1; k <= 2; k++)
                t.g[i][j] = (t.g[i][j] + a.g[i][k] * b.g[k][j]) % mod;
    return t;
}
void qmi(ll k) {
    init();
    while(k) {
        if(k & 1) E = mul(E, v);
        v = mul(v, v);
        k >>= 1;
    }
}
void print(Matrix a) {
    for (int i = 1; i <= 2; i++) {
        for (int j = 1; j <= 2; j++)
            cout << a.g[i][j] << " ";
        cout << endl;
    }
}
int main() {
    int n, m; cin >> n >> m;
    n = __gcd(n, m);
    if(n <= 2) {
        cout << 1 << endl;
        return 0;
    }
    qmi(n - 1);
    // print(E);
    cout << E.g[1][1] << endl;
    return 0;
}

例题7： 这个勇者明明超强却过分慎重

这个勇者明明超强却过分慎重

#include <bits/stdc++.h>
#pragma GCC optimize(2)
#pragma GCC optimize(3)
using namespace std;
#define js ios::sync_with_stdio(false);cin.tie(0); cout.tie(0)
typedef long long ll;
inline ll read() { ll s = 0, w = 1; char ch = getchar(); while (ch < 48 || ch > 57) { if (ch == '-') w = -1; ch = getchar(); }    while (ch >= 48 && ch <= 57) s = (s << 1) + (s << 3) + (ch ^ 48), ch = getchar();    return s * w; }
const int mod = 666666;
const int N = 2; //矩阵规模
const int M = 2;
struct Node {
    ll matrix[N][M];//结构体中的矩阵
    Node() {//默认构造函数
        memset(matrix, 0, sizeof(matrix));
    }
    void one() {//单位矩阵
        for (int i = 0; i < N; ++i)
            matrix[i][i] = 1;
    }
    Node operator*(Node other) {//矩阵运算重载*运算符
        Node ans;//记录乘积
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                for (int k = 0; k < N; k++) {
                    ans.matrix[i][j] += matrix[i][k] * other.matrix[k][j];
                    ans.matrix[i][j] %= mod;
                }
        return ans;
    }
};
Node power(Node a, ll b) {//快速幂求a的b次方
    Node res;
    res.one();//单位矩阵
    while (b) {
        if (b & 1)
            res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
int main() {
    Node st, p;
    // [f[1], f[2]] = [4, 233];
    st.matrix[0][0] = 4;
    st.matrix[0][1] = 233;
    // f(n) = 4 * f(n - 1) + 3 * f(n - 2)
    // 0 3
    // 1 4
    p.matrix[0][1] = 3;
    p.matrix[1][0] = 1;
    p.matrix[1][1] = 4;
    int n, m;
    while(~scanf("%d %d", &n, &m))
        printf("%d\n", m - (st * power(p, n - 1)).matrix[0][0]);
    return 0;
}

ps: 矩阵拓展

文章标签：
云数据库 ClickHouse
Java
CDN
dm2e66eopcgq6
目录
相关文章
极客李华
|
6月前
|
Java C++
简单斐波那契
简单斐波那契
极客李华
77 0
菊头蝙蝠
|
6月前
|
Java
leetcode-509：斐波那契数
leetcode-509：斐波那契数
菊头蝙蝠
478 0
龙腾九州
|
14天前
斐波那契数列
【10月更文挑战第19天】斐波那契数列。
龙腾九州
11 3
游客rcxtdbgrolahs
|
2月前
|
Java
01_斐波那契数列
01_斐波那契数列
游客rcxtdbgrolahs
91 5
肥猪lele01
|
5月前
|
存储 算法
精益求精——斐波那契数列的logn解法
精益求精——斐波那契数列的logn解法
肥猪lele01
61 0
会洗碗的CV工程师
|
6月前
|
机器学习/深度学习 算法
斐波那契数列和斐波那契数
【2月更文挑战第6天】
会洗碗的CV工程师
52 1
斐波那契数列和斐波那契数
翔宇1
|
6月前
斐波那契（快速矩阵幂）
斐波那契（快速矩阵幂）
翔宇1
33 0
DyeDD
|
11月前
leetcode 509 斐波那契数
今天重新看了下动态规划， 它和递归的区别就是，它是自下而上的。 还了解到状态压缩 如果我们发现每次状态转移只需要 DP table 中的一部分，那么可以尝试用状态压缩来缩小 DP table 的大小，只记录必要的数据 于是就刷了这道简答题,用到了状态压缩
DyeDD
38 0
宏阳李老师
（1188：1201：）斐波那契数列
（1188：1201：）斐波那契数列
宏阳李老师
145 0
Crossin的编程教室
|
机器学习/深度学习 开发工具
斐波那契数列的四种实现
在编程教程中提到斐波那契数列，通常都是用来讲解递归函数。当一个关于 N 的问题可以转换为关于 N - k 的同样问题时，它就可以尝试用递归的思路来解决。
Crossin的编程教室
105 0