【题解】数列-13（矩阵快速幂）

本题涉及到矩阵快速幂算法，如果对矩阵操作不熟悉的话可以先做一下这道题：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：特殊的斐波那契数列