斐波拉契加强版

题目：
对于斐波拉契经典问题，我们都非常熟悉，通过递推公式F(n) = F(n - 1) + F(n - 2)，我们可以在线性时间内求出第n项F(n)，现在考虑斐波拉契的加强版，我们要求的项数n的范围为int范围内的非负整数，请设计一个高效算法，计算第n项F(n-1)。第一个斐波拉契数为F(0) = 1。
给定一个非负整数，请返回斐波拉契数列的第n项，为了防止溢出，请将结果Mod 1000000007。
输入：3
输出：2
解析：
1. 首先解释下加强版是什么意思，简单来说就是O(n)的复杂度不能编译通过，必须要求复杂度达到O(log(n))菜可以的哟。
2. 数字右移用0填充，操作相当于除以数字2，数字左移用1填充。
3. 找规律，可用数学归纳法证明；
初始值：f(0) = 1, f(1) = 1, f(2) = 2, f(3) = 3, f(4) = 5…
以f(10)为例子找规律：f(10)=f(9)+f(8)=2f(8)+f(7)=3f(7)+2f(6)=5f(6) + 3f(5)=f(4)f(6)+f(3)f(5) …
发现规律：F(n) = F(k)F(n-k) + F(k-1)F(n-k-1), k>=1
推导出如下公式:
F(2n) = F(n) F(n) + F(n-1) F(n-1), n>=1
F(2n+1) = F(n+1) F(n) + F(n) F(n-1), n>=1
代码：

import java.util.*;

public class Fibonacci {
    public int getNthNumber(int n) {
        // write code here
        // 利用矩阵来做工作 使用long存储数据
        long[][] base={{1,1},{1,0}};
        long[][] ret={{1,0},{0,1}};
        // 利用while来进行二分法，用来实现复杂度的减少
        while(n!=0){
            if(n%2==1)
                // 计算并更新二维数组
                ret=MultMetri(ret,base);
            base=MultMetri(base,base);
            // 数字右移，相当于除以2，这样子就实现了二分法，
            n=n>>1;
        }
        return (int)(ret[0][0]);
    }
    // 传入两个二维数组，也就是2* 2*2
    public static long[][] MultMetri(long[][] ret,long[][] base){
        // 创建临时数组
        long[][] tmp=new long[2][2];
        // 两个for循环，用于计算临时数组，然后再次执行双for循环赋值
        for(int i=0;i<2;i++)
            for(int j=0;j<2;j++)
                tmp[i][j]=(ret[i][0]*base[0][j]+ret[i][1]*base[1][j])%1000000007;
        for(int k=0;k<2;k++)
            for(int q=0;q<2;q++)
                ret[k][q]=tmp[k][q];
        return ret;
    }
}