IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 线性递推转化为矩阵快速幂 -> 正文阅读

[数据结构与算法]线性递推转化为矩阵快速幂

方程的根通过移项可以得到低次向高次的线性递推,通过变形目标式得到目标式的线性递推,最后用矩阵乘法快速幂处理

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod =998244353;
int nn=3;
const int maxn=10;
struct mat{
    ll m[maxn][maxn];
    mat(){
        memset(m,0,sizeof(m));
    }
    mat operator * (const mat b) const {
        mat ans;
        for(int i=1;i<=nn;++i)
        {
            for(int j=1;j<=nn;++j)
            {
                for(int k=1;k<=nn;++k)
                {
                    ans.m[i][j]+=m[i][k]*b.m[k][j];
                    ans.m[i][j]%=mod;
                    ans.m[i][j]+=mod;
                    ans.m[i][j]%=mod;
                }
            }
        }
        return ans;
    }
};
mat pow_mat(mat a,ll b)
{
    mat ans;
    for(int i=1;i<=nn;++i)
    {
        ans.m[i][i]=1;
    }
    while(b)
    {
        if(b&1)
            ans=ans*a;
        a=a*a;
        b>>=1;
    }
    return ans;
}
int main ()
{
    ll s,t,u,n,mm;
    cin>>n>>mm>>s>>t>>u;
    mat a,b,ans;
    nn=3;
    a.m[1][1]=s;
    a.m[1][2]=-t;
    a.m[1][3]=u;
    a.m[2][1]=1;
    a.m[3][2]=1;
    b.m[1][1]=s;
    b.m[1][2]=1;
    b.m[2][1]=-t;
    b.m[2][3]=1;
    b.m[3][1]=u;
    ans.m[1][2]=-1;
    ans.m[2][1]=1;
    a=pow_mat(a,n);
    b=pow_mat(b,mm);
    a=a*ans;
    a=a*b;
    cout<<a.m[nn][nn];
    return 0;
}

  数据结构与算法 最新文章
【力扣106】 从中序与后续遍历序列构造二叉
leetcode 322 零钱兑换
哈希的应用:海量数据处理
动态规划|最短Hamilton路径
华为机试_HJ41 称砝码【中等】【menset】【
【C与数据结构】——寒假提高每日练习Day1
基础算法——堆排序
2023王道数据结构线性表--单链表课后习题部
LeetCode 之 反转链表的一部分
【题解】lintcode必刷50题<有效的括号序列
上一篇文章      下一篇文章      查看所有文章
加:2022-05-07 11:22:23  更:2022-05-07 11:24:48 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁

360图书馆 购物 三丰科技 阅读网 日历 万年历 2024年11日历 -2024/11/26 3:39:38-

图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码