论文部分内容阅读
在算法竞赛中,有一类常见的可以使用线性递推来求解的问题,但其中有部分问题求解所需的递推次数过多,以至于无法在规定的时间范围内完成求解.本文介绍了名为矩阵快速幂的算法的基本原理和推导过程,分析了时间复杂度,对不同情况下的转移矩阵和状态向量的构造进行了剖析.总结了可以使用矩阵快速幂优化时间复杂度的一类问题的特点.