先看题把：
对于斐波拉契经典问题，我们都非常熟悉，通过递推公式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关键在于设计一个算法，可以快速的计算第n个数，我们来看递推公式，将其写成矩形相乘的形式：
接着我们就可以用快速幂了（http://blog.csdn.net/zjucor/article/details/70146583），关键在于根据递推公式写出矩阵表达式的形式
package Fabnaci; /* * 就用long[][]数组吧 * long = int * int 是没有效果的 */ public class Fibonacci { public int getNthNumber(int n) { // write code here long[][] a = new long[][]{ new long[]{1,1}, new long[]{1,0} }; long[][] c = matrixPower(a, n); return (int)c[0][0]; } public long[][] matrixPower(long[][] a, int n) { // 注意：初始化为单位矩阵 long[][] b = new long[a.length][a.length]; for(int i=0; i<a.length; i++) b[i][i] = 1; while(n != 0) { if((n & 1) != 0) b = helper(b, a); n = n >> 1; a = helper(a, a); } return b; } public long[][] helper(long[][] a, long[][] b) { long[][] c = new long[a.length][a.length]; for(int i=0; i<a.length; i++) for(int j=0; j<a.length; j++) for(int k=0; k<a.length; k++) { long t = a[i][k] * b[k][j]; c[i][j] += (t % 1000000007); c[i][j] %= 1000000007; } return c; } }再看另外一个：
在农场中，奶牛家族是一个非常庞大的家族，对于家族中的母牛，从它出生那年算起，第三年便能成熟，成熟的母牛每年可以生出一只小母牛。即母牛从出生开始的第三年便能做妈妈。最开始农场只有一只母牛，它从第二年开始生小母牛。请设计一个高效算法，返回第n年的母牛总数，已知n的范围为int范围内的正整数。
给定一个正整数n，请返回第n年的母牛总数，为了防止溢出，请将结果Mod 1000000007。
测试样例： 6 返回：9 明显用DP：F(n) = F(n-1) + F(n-3)，用的是3阶方阵的相乘
其实根据递推公式写矩形形式是有规律的，如下：
之前在博客http://blog.csdn.net/zjucor/article/details/70146583上写的那道题也是用这种方法，不过隐藏的比较难发现用快速幂而已
