【求解答】有道笔试，后台开发，编程第3题怎么做？

快速幂 这是斐波那契快速幂的讲解： 当N很小的时候，我们直接通过递推公式便可以计算。当N很大的时候，只要我们的电脑足够好，我们仍然可以直接通过递推公式来计算。 但是我们学算法的，总是这样直接枚举不是显得很Low么，所以我们要用一个好的算法来加速(装X)。 事实上，对于这种线性递推式，我们可以用矩阵乘法 来求第n项。对于本题Fibonacci数列，我们希望找到一个2x2的矩阵M，使得(a, b) x M = (b, a+b)，其中(a, b)和(b, a+b)都是1x2的矩阵。 显然，只需要取M = [0, 1; 1, 1]就可以了： 进一步得到： 那么接下来的问题是，能不能快速的计算出M^n？我们先来分析一下幂运算。由于乘法是满足结合律的，所以我们有： 不妨将k[1]..k[j]划分的更好一点？ 其中(k[1],k[2]...k[j])2表示将n表示成二进制数后每一位的数字。上面这个公式同时满足这样一个性质： 结合这两者我们可以得到一个算法： 1. 先计算出所有的{a^1, a^2, a^4 ... a^(2^j)}，因为该数列满足递推公式，时间复杂度为O(logN) 2. 将指数n二进制化，再利用公式将对应的a^j相乘计算出a^n，时间复杂度仍然为O(logN) 则总的时间复杂度为O(logN) 这种算法因为能够在很短时间内求出幂，我们称之为“快速幂”算法。

暴力的话，应该是60%啊

60

暴力同60，后来想的是根据k的次数应该有个规律

同暴力60%

Xi= Cn 1Xi + Cn 2Xi+1 + ..... 要先把这个系数先算出来。。。。

暴力是60，我猜你忘记取模了

暴力60%飘过

有个思路：就以题目给得例子来说 3 2 1 2 3 输出  8 9 7 8=1+2*2+3* 1 9=2+3*2+1*1 7=3+1*2+2*1

思路没说完整：就以题目给得例子来说 3 2 1 2 3 输出  8 9 7 8=1+2*2+3* 1 9=2+3*2+1*1 7=3+1*2+2*1 那么 3 4 1 2 3 这个输入呢？ 输出是：33 31 32 33=8+9*2+7*1 31=9+7*2+8*1 32=7+8*2+9 也就是说，第一次能计算出k=n-1的情况，第二次能计算出k=2*（n-1）的情况，第三次能计算出k=3*（n-1）的情况，时间复杂度由原来的K*N变为K*N/（N-1） 不过还有%100这个条件没考虑清楚

我也取模了，也是10%....是超过了规定的空间。

你考虑到要先保存第一个数吗，最后一个数加的是原先的第一个数，不是改变后的第一个数