java版保证无错题解（蓝桥杯2014年第五届真题-斐波那契）

解题思路:
    首先请大家自行了解线性代数中的矩阵乘法，矩阵的快速幂，求余数的数学化简公式:

       1. (M＋N) mod q=(（M mod q）+（N mod q）) mod q；

       2.求M*N除以q的余数，就等于M除以q的余数 乘以 N除以q的余数。

（本人比较懒，只是这题做得脑壳疼(因为菜啊!)，且这题没有一个java题解，顺手记录下）。由f(n) = f(n + 2) - f(n + 1)得斐波那契数列前n项和S(n)=f(n + 2) - 1。另外C++的题解中有几个是有问题的，大家可以用n = 2,m = 4, p = 6去检验下，正确答案是2，而那些错答案是-1或5。

注意事项:
    使用BigInteger避免爆long。

    其实题目很坑，如果n + 2 > m时并且m特别大时代码是没有办法跑完的，如n = 165165161665151622 m = 1651515615156555 p = 13515

    但是题目的测试点中没有这样的数据（只能说题纲有不小的问题）。

参考代码:

import java.math.BigInteger;
import java.util.Scanner;
@SuppressWarnings({"all"})
public class Main {
   static BigInteger p2;//其实就是p,请不要误解。
   static boolean f;//标记能否在矩阵乘法中队p求余。
   static BigInteger fm2;//求S(n)时加速用的，当然也可以不用，在n远小于m时使用会更加慢
   public static void main(String[] args) {
       Scanner scan = new Scanner(System.in);
       BigInteger n = scan.nextBigInteger();
       BigInteger m = scan.nextBigInteger();
       p2 = scan.nextBigInteger();
       n = n.add(BigInteger.valueOf(2));
       BigInteger sum;
       if(n.compareTo(m) <= 0){//情况1：n + 2<= m，答案=(f(n+2)-1)%p，此时在算f(n)时可以随时对p求余。

           f = true;
           sum = fib(n).subtract(BigInteger.ONE);

           System.out.println(sum.mod(p2));

       }else {//情况2:n + 2 > m，答案=(f(n+2)-1)%f(m)%p，中间隔有f(m)，此时在算f(n)时不能够对p求余。

           f = false;
           BigInteger fm = fib(m);
           fm2 = fm;
           sum = fib(n).subtract(BigInteger.ONE);
           System.out.println(sum.mod(fm).mod(p2));
       }
   }
   public static BigInteger fib(BigInteger n){//快速幂法求斐波那契数列第n项。
       if(n.equals(BigInteger.ONE) || n.equals(BigInteger.valueOf(2))){
           return BigInteger.valueOf(1);
       }
       BigInteger[][] arr1 = new BigInteger[][]{{BigInteger.valueOf(1),BigInteger.valueOf(1)}};
       BigInteger[][] arr2 = new BigInteger[][]{{BigInteger.valueOf(1),BigInteger.valueOf(1)},{BigInteger.valueOf(1),BigInteger.ZERO}};
       BigInteger[][] ans = multiply(arr1,pow2(arr2,n.subtract(BigInteger.valueOf(2))));
       return ans[0][0];
   }
   public static BigInteger[][] pow2(BigInteger[][] t,BigInteger p){//求矩阵p次幂
       BigInteger[][] res = new BigInteger[t.length][t.length];
       for (int i = 0; i < res.length; i++) {
           for (int j = 0; j < res.length; j++) {
               res[i][j] = i == j ? BigInteger.ONE : BigInteger.ZERO;
           }
       }
       for(;!p.equals(BigInteger.ZERO);p = p.divide(BigInteger.valueOf(2))){
           if(p.mod(BigInteger.valueOf(2)).equals(BigInteger.ONE)){
               res = multiply(res,t);
           }
           t = multiply(t,t);
       }
       return res;
   }
   public static BigInteger[][] multiply(BigInteger[][] target,BigInteger[][] target2){//矩阵乘法
       BigInteger[][] res = new BigInteger[target.length][target2[0].length];
       for(int i = 0;i < res.length;i++){
           for(int j = 0;j < res[0].length;j++){
               res[i][j] = BigInteger.ZERO;
           }
       }
       int r1 = 0,c1;
       int c2;//r2是等于c1的
       for (; r1 < res.length; r1++) {
           for(c2 = 0;c2 < target2[0].length;c2++){
               for(c1 = 0;c1 < target[0].length;c1++){
                   if(f) {
                       res[r1][c2] = res[r1][c2].add(target[r1][c1].multiply(target2[c1][c2]).mod(p2)).mod(p2);
                   }else {
                       if(fm2 != null) {
                           res[r1][c2] = res[r1][c2].add(target[r1][c1].multiply(target2[c1][c2]).mod(fm2).mod(fm2));
                       }else{
                           res[r1][c2] = res[r1][c2].add(target[r1][c1].multiply(target2[c1][c2]));
                       }
                   }
               }

           }
       }
       return res;
   }
}