斐波那契数列和，矩阵快速幂

本题我写的内存超限，不要copy我的代码，但是答案都是正确的，不超出时间，做笔记，以后回来再跟进。

有高手也可以给我指出一下怎么提高代码内存优化

解题思路:

首先先要了解什么是快速幂

快速幂的意思是，像2的n次方，用正常的循环就可以解决，但是当这个n很大的时候，就没有办法使用java中Math.pow来做了。

那怎么用快速幂呢，比如10，我们可以将他转化成2进制1010，就变成了2^3+2^1，时间复杂度变成了log2n，大大优化了。具体操作如下：

1、判断当前数是否为偶数，如果不是偶数，那么就要-1变成偶数，并且先提前将x的1次方给result

2、如果是偶数或者是变成偶数之后，将n/=2（这里用2进制做效率更高），将底数x翻倍，如10^6变成100^3

3、到n=1的时候，已经翻倍成最大了，一次性赋值给result，再次判断为奇数，n变为0，退出循环

参考代码:

public class Main {
    private static int mod = 1000;

    public static void main(String[] args) {
        int x = 2;
        int n = 1000000000;
        long startTime = System.currentTimeMillis();
        int result = fastPower(x,n);
        System.out.println("结果是："+result);
        long endTime = System.currentTimeMillis();
        System.out.println("运行时间为："+(endTime-startTime)+" ms. ");
    }

    private static int fastPower(int x, int n) {
       int result=1;
       while(n>0) {
    	   if((n&1)==1) {
    		  n-=1;
    		  result*=x;
    		  result%=mod;
    	   }
    	   	n>>=1;
    		x*=x;
    		x%=mod;
    	   
       }
       return result;
    }
}

再了解矩阵的快速幂

了解了快速幂之后，矩阵快速幂也是一样的，把当前矩阵带入到上面的x中就可以了，方法很简单。具体操作我在下面讲

斐波那契数列和

当然不可能一个个的数字往上加，时间必然会超限。

f(n+2)=f(n+1)+f(n)

f(n+1)=f(n)+f(n-1)

......

S(n)-S(n-1)=f(n);

S(n)=f(n+2)-f(2);

递推一下，可以得到公式S(n)=f(n-2)-1;

还有一个问题是f(n)怎么求？看下面这张图应该明白了，字有点丑哈

最后就到本题了

我真的巨想吐槽，可恶的java，全是BigInteger，写的太麻烦了，要是有longlong就好了，用BigInteger也用不了位运算，用不了快读快些。哎，估计就出现在这里的内存问题吧

先写一个矩阵相乘的方法，方便矩阵快速幂的运算，这个应该都会，有个问题就是其实矩阵相乘ikj会优化一部分，但是就这样把，水平有限

然后就是矩阵快速幂的运算，如果正常创建一个矩阵默认值会是0，但是BigInteger没有默认值要自己设。然后把数组全部初始化一下。用下上面的快速幂方法，如果是奇数，先把一个当前矩阵给res，如果不是就当前矩阵平方，n/=2

最后调用方法，我可能这里算的有些问题，比如输入的第n个的mutiply（n）会求得n+1个的值，哎无所谓了，程序能跑就行，懒得改了，[0][1]就是求得的值。带入计算即可。

import java.math.BigInteger;
import java.util.Scanner;


public class Main{
	public static void main(String[] args)  {
		Scanner sc=new Scanner(System.in);
		BigInteger n=sc.nextBigInteger();
		BigInteger m=sc.nextBigInteger();
		BigInteger p=sc.nextBigInteger();
		BigInteger[][] fn=mulpow(n.add(BigInteger.ONE));
		BigInteger[][] fm=mulpow(m.subtract(BigInteger.valueOf(1)));
		BigInteger ans=(fn[0][1].subtract(BigInteger.ONE)).mod(fm[0][1]).mod(p);
		System.out.println(ans);
	}
	
	//矩阵快速幂算法
	public static BigInteger[][] mulpow(BigInteger n){
		BigInteger[][] a=new BigInteger[2][2];
		a[0][0]=a[0][1]=a[1][0]=BigInteger.ONE; //a为1,1,1,0矩阵
		a[1][1]=BigInteger.ZERO;
		BigInteger[][] res=new BigInteger[2][2];
		// 将res设为单元矩阵 相当于整数快速幂中结果的设为1
		for (int i = 0; i < 2; i++) {
			for(int j=0;j0) {
			if(n.mod(BigInteger.TWO).compareTo(BigInteger.ZERO)!=0) {
				res=MatrixMutiply(res,a);
			}
			a=MatrixMutiply(a,a);
			n=n.divide(BigInteger.TWO);
		}
		return res;
	}
	//矩阵乘法
	public static BigInteger[][] MatrixMutiply(BigInteger[][] a,BigInteger[][] b){
		BigInteger[][] ans=new BigInteger[a.length][b[0].length];
		for(int i=0;i<a.length;i++) {
			for(int j=0;j<b[0].length;j++) {
				ans[i][j]=BigInteger.valueOf(0);
			}
		}
		for(int i=0;i<a.length;i++) {
			for(int j=0;j<b[0].length;j++) {
				for(int k=0;k<b.length;k++) {
					ans[i][j]=ans[i][j].add(a[i][k].multiply(b[k][j]));
				}
			}
		}
		return ans;
	}
	
}