【题解】数列-13(矩阵快速幂)

发布时间:2023-05-01 11:25:20
贴主:易向晚来适
热度:5
正在讨论:P4197 - 数列-13 题目传送门

易向晚来适 2023-06-05

本题涉及到矩阵快速幂算法,如果对矩阵操作不熟悉的话可以先做一下这道题:2495:矩阵乘法

接下来进入正题,通过观察数据范围,我们发现待求项数 m 最大可达 20亿,虽然本题时间给了 8s,但想暴力求解 10 组拉满的数据还远远不够

因此我们引入矩阵快速幂算法,顾名思义,其原理和快速幂是一样的,只不过乘数由数字变成了矩阵,而矩阵的乘积刚好可以为我们加速递推

考虑矩阵的转移关系,以 3 阶为例,如何由 [f(n),f(n-1),f(n-2)] 转移到 [f(n + 1),f(n),f(n-1)]?

因此我们需要构造一个转移矩阵来帮助转移,易推该矩阵为 [[1,1,0], [1,0,1], [1,0,0]],即第一列全部为 1(作为转移)后面的每行保存对应数字

做一次矩阵乘法就是向后推一项,由于矩阵满足结合律,因此我们只需要让转移矩阵自乘 n 次就可以了,最后再让我们预处理的基础矩阵去乘

相关题目推荐:

2370:斐波那契数列-2

3425:特殊的斐波那契数列

(4)

Copyright 2016 - 2024 XUJC ACM Team
闽ICP备2020022076号-1