平凡的小白

未归档

题解(64)

/ 注册

全部文章 / 未归档（共2篇）

斐波那契

小白月赛20戳我传送题目大意：输出前斐波那契数列前n项平方和，1<=n<=1e18。前备知识：快速幂和矩阵，可以进我的博客了解一下，小白非常容易理解：戳我了解思路：斐波那契数列前n项平方和有递推式：前n项平方和等于 f[n] * f[n+1]。因为n非常大，用递归的思路去求肯定超时...

矩阵快速幂

2020-04-17

1 694

矩阵快速幂求斐波那契数列

快速幂： 1.求5^19，19个5相乘当然可以算出来，但是当指数特别大的时候O(n)就不行了，必须要O(logn)的算法，也就是根据位运算来求解。19的二进制是（10011）5^19=5^1 * 5^2 * 5^16;指数对应的二进制如下：1---00001,2---00010,16---1000...

矩阵快速幂

2020-04-17

1 787