本题涉及到矩阵快速幂算法,如果对矩阵操作不熟悉的话可以先做一下这道题: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 次就可以了,最后再让我们预处理的基础矩阵去乘
相关题目推荐: