你的位置:首页 > 信息动态 > 新闻中心
信息动态
联系我们

关于矩阵快速幂的学习总结

2021-11-2 9:32:57
#include <bits/stdc++.h>
using namespace std;
const long long MOD = 1e9+7;
struct Matrix//声明矩阵结构体,定义矩阵乘法,以及单位矩阵
{
    long long a[3][3];
    Matrix()
    {
        memset(a, 0, sizeof(a));
    }
    Matrix operator*(const Matrix &b) const
    {
        Matrix res;
        for (int i = 1; i <= 2; i++)
        {
            for (int j = 1; j <= 2; j++)
            {
                for (int k = 1; k <= 2; k++)
                {
                    res.a[i][j] = (res.a[i][j]+a[i][k]*b.a[k][j])%MOD;//疑问点
                }
            }
        }
        return res;
    }
    void setE(int x)
    {
        for (int i = 1; i <= 2; i++)
        {
            a[i][i] = x;
        }
        return ;
    }
};
Matrix power(Matrix m, long long n)//矩阵快速幂
{
    Matrix ans;
    ans.setE(1);
    while (n > 0)
    {
        if (n&1)
        ans = ans* m;
        m = m * m;
        n >>= 1;
    }
    return ans;
}
void solve()
{
    Matrix trans, f;
    trans.a[1][1] = trans.a[1][2] = trans.a[2][1] = 1;//给转化矩阵赋值
    f.a[1][1] = f.a[2][1] = 1;//给递推矩阵赋值
    long long n;
    scanf("%lld", &n);
    trans = power(trans, n-2);//转化
    for (int i = 1; i <= 2; i++)
    {
        for (int j= 1;j <= 2; j++)
        printf("%d ", trans.a[i][j]);
        printf("\n");
    }
    trans = trans*f;
    printf("%lld\n",trans.a[1][1] % MOD);//取模防爆数据
    return;
}
int main(void)
{
    int t;
    scanf("%d", &t);
    while (t--)
    {
        solve();
    }
    return 0;
}

先上一个板子,非常之好用

首先我们得明白矩阵的乘法,学了线代的同学应该都明白,一一对应相乘,不懂就去找宋老师

链接配上:《线性代数》高清教学视频 “惊叹号”系列 宋浩老师_哔哩哔哩_bilibili《线性代数》全程高清教学视频 “惊叹号”系列主讲:宋浩 老师 博士,副教授,网红数学老师。 新浪微博:宋浩老师_ice_mouse目录: 第一章 行列式 第二章 矩阵 第三章 向量 第四章 线性方程组 第五章 特征值与特征向量 第六章 二次型更多宋老师的视频,下载手机Ahttps://www.bilibili.com/video/BV1aW411Q7x1?spm_id_from=333.999.0.0

 然后就是对应的代码了