参考：斐波那契数列为什么那么重要，所有关于数学的书几乎都会提到？
快速幂
1.快速幂
快速幂算法的核心思想就是每一步都把指数分成两半，而相应的底数做平方运算。这样不仅能把非常大的指数给不断变小，所需要执行的循环次数也变小，而最后表示的结果却一直不会变。
int Qpow( int a,int n){int ans = 1;while(n){if(n&1) ans*=a ;a *= a ;n>>= 1;}return ans;} 2.矩阵快速幂实现求斐波那契数列第n项 1.Description
求斐波那契数列第n项模1000000007的值，其中f(1)=f(2)=1，fib(n)=fib(n-1)+fib(n-2)(n>2)。
输入
一个数 n，保证n在longlong范围内。
输出
一个数，斐波那契数列第n项模1000000007。
2.Example 样例输入4样例输出3 3.Solution
因为数特别多，超过long，而且一个一个加超时，因此需要用其他的方法。
import java.util.*;public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); System.out.println(fast_mod(n)); } public static long[][] multi(long[][] ans,long[][] base){ long[][] temp = new long[2][2]; for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { for(int k=0;k<2;k++) { temp[i][j] = (temp[i][j]+(ans[i][k]*base[k][j])%1000000007)%1000000007; } } } return temp; } public static long fast_mod(long n ) { long[][] base = {{1,1},{1,0}}; long[][] ans = {{1,0},{0,1}};//单位矩阵 while(n>0) { if((n&1)==1) { ans = multi(ans, base); } base = multi(base, base); n >>= 1; } return ans[0][1]; }} 3.快速幂实现求斐波那契数列前n项平方和
代码几乎和2中的一样，就改了一下快速幂的输出。这里主要是将前n项平方和转化成求面积，因此只需要求出来第n项和第n-1项的乘积即可。
class Test{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); System.out.println(fast_mod(n)); } public static long[][] multi(long[][] ans,long[][] base){ long[][] temp = new long[2][2]; for(int i=0;i<2;i++) { for(int j=0;j<2;j++) { for(int k=0;k<2;k++) { temp[i][j] = (temp[i][j]+(ans[i][k]*base[k][j])%1000000007)%1000000007; } } } return temp; } public static long fast_mod(long n ) { long[][] base = {{1,1},{1,0}}; long[][] ans = {{1,0},{0,1}};//单位矩阵 while(n>0) { if((n&1)==1) { ans = multi(ans, base); } base = multi(base, base); n >>= 1; } return (ans[0][1]*((ans[0][1]+ans[1][1])%1000000007))%1000000007; }}