【概述】

线性递推关系是组合计数中一种常见的递推关系，关系式为：

最著名的线性递推关系就是 Fibonacci 数列，有：f(1)=f(2)=1,f(n)=f(n-1)+f(n-2)

对于线性递推关系，直接利用递推式，需要在 O(nd) 的时间内才能求出 F(n)，时间无法承受，可以考虑借助矩阵来进行优化。

现在已经有了：，那么再加上  这种显然成立的式子，于是有：

根据矩阵乘法的定义，即有：，于是可以利用矩阵快速幂来解决，时间复杂度仅为

例如，对于递推公式：

可以构造矩阵：

化简后：

由于 f(0)=0，f(1)=1，那么有：

故答案为：

因此矩阵快速幂求出 A 后即得答案

关于矩阵快速幂：点击这里

【例题】

Reading comprehension（HDU-4990）：点击这里

233 Matrix（HDU-5051）：点击这里

Jzzhu and Sequences（CF-450B）：点击这里

Bear in the Field（CF-385E）：点击这里

M斐波那契数列（HDU-4549）(斐波那契矩阵构造+费马小定理)：点击这里

总结

以上是生活随笔为你收集整理的线性代数 —— 线性递推关系的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。