导入

在第一次学dp的时候，相信大家都敲过 f(n)=f(n-1)+f(n-2) 这种斐波那契数列，为了求出f(n)如果枚举每种情况，时间复杂度为 O(n)。对于这个问题来介绍一种复杂度O(logn)的方法。

数学分析

对于像 f(n)= af(n-1)+bf(n-2) 这种函数关系，可以把他们看成矩阵运算 A=base*B （base为关系矩阵）：

$~~~~~~~~~~~$ $ \begin{pmatrix} f(n) \\ ?\\ \end{pmatrix} $ = $ \begin{pmatrix} a & b \\ ? & ? \\ \end{pmatrix} $ * $ \begin{pmatrix} f(n-1) \\ f(n-2)\\ \end{pmatrix} $

然而这个矩阵还不完整我们可以再构造一下；

$~~~~~~~~~~~$ $ \begin{pmatrix} f(n) \\ f(n-1)\\ \end{pmatrix} $ = $ \begin{pmatrix} a & b \\ 1 & 0 \\ \end{pmatrix} $ * $ \begin{pmatrix} f(n-1) \\ f(n-2)\\ \end{pmatrix} $

这样就可以发现，在每次从 f(n-1),f(n-2) 转移到 f(n),f(n-1)的过程中，系数矩阵base是不变的而且矩阵的乘法满足结合律，这样就有$f(n+2),f(n+1)=base^n*f(2),f(1)$的等式成立，而后只需要计算$base^n$的值即可，而计算base^n可以使用快速幂来简化计算：对base进行自乘，再对 n的bit位为1的地方累成即可。要注意的是由于矩阵不满足交换律，必须把自乘过的系数矩阵放左侧。

模板

时间复杂度O(k^3*logn)
def mul(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
    return [[sum(x * y for x, y in zip(row, col)) for col in zip(*b)]
            for row in a]

def pow_mul(a: List[List[int]], n: int, f0: List[List[int]]) -> List[List[int]]:
    res = f0
    while n:
        if n & 1:
            res = mul(a, res)
        a = mul(a, a)
        n >>= 1
    return res

总结

当得到的转移方程是一个n阶k项的递推数列，而且这个方程的项少于200，而转移的次数大于10**9时，可以考虑用这个方法