斐波那契数列

PREV-29

• 这题的难度很大，主要是题目中的要求数据量太大，1^18，这不管是运行时间会超时，而且累加的话也会超出long型的大小。
• 我采用多种方法来求解这道题目，逐步优化算法。

1. 基础解法：直接暴力求解斐波那契数列（得分：40）

我们深入考虑斐波那契的性质：
1.1 f(x)=f(x-1)+f(x-2)<=>f(x+1)=f(x)+f(x-1)<=>f(x)=f(x+1)-f(x-1)
* -->∑(f(i))=f(n)+f(n+1)-1<=>f(n+2)-1
1.2 原题等价于(f(n+2)-1)%f(m)%mod <=>f(n+2)%f(m)%mod-1
* -->如果m>=n+2,等价于f(n+2)%mod-1;
* -->否则，等价于一定要求解f(m)

2. 优化1：在第一种方法的基础上，使用矩阵快速幂来求解斐波那契数列（得分40分）

矩阵的幂的性质可以用来求解斐波那契数列。

3. 优化2：由于第二种方法虽然加速了运算，但是没有解决数据大小超出long型的限制问题，所以这里在求斐波那契的同时将mod模带进去运算（得分：60分）

在求解斐波那契的同时可以将mod带进去求解，可以解决所有数据相加太大的问题。

4. 优化3：在第三种方法上，已经解决了超出long的问题，但是算法的效率还是不太高，仍然无法在1s内处理大量的数据。优化三进一步使用快速幂来求解两数相乘的问题。得分（100分）

/*输入格式
　　输入为一行用空格分开的整数 n m p (0 < n, m, p < 10^18)
输出格式
　　输出为1个整数，表示答案*/
//f(x)=f(x-1)+f(x-2)<=>f(x+1)=f(x)+f(x-1)<=>f(x)=f(x+1)-f(x-1)
//-->∑(f(i))=f(n)+f(n+1)-1<=>f(n+2)-1
//原题等价于(f(n+2)-1)%f(m)%mod <=>f(n+2)%f(m)%mod-1
//-->如果m>=n+2,等价于f(n+2)%mod-1;
//-->否则，等价于一定要求解f(m)
package lanQiao;

import java.util.Scanner;

public class 斐波那契 {
    static long n, m, p;

    // 40分：当数据太大，long型也存不下所有的和，以及超时问题
    static void solve1() {
        long a = 1, b = 1;
        if (m > n + 2) {
            for (int i = 3; i <= n + 2; i++) {
                long t = a;
                a = b;
                b += t;
            }
            // b就是n+2项
            System.out.println(b % p - 1);
        } else {
            long fibM = 0, fibN2;
            for (int i = 3; i <= n + 2; i++) {
                long t = a;
                a = b;
                b += t;
                if (i == m) {
                    fibM = b;
                }
            }
            fibN2 = b;
            System.out.println((fibN2 % fibM) % p - 1);
        }
    }

    private static class M {
        long[][] data = new long[2][2];
    }

    // 将两个2*2的矩阵相乘
    static M mul(M m1, M m2) {
        M fin = new M();
        fin.data[0][0] = m1.data[0][0] * m2.data[0][0] + m1.data[0][1] * m2.data[1][0];
        fin.data[0][1] = m1.data[0][0] * m2.data[0][1] + m1.data[0][1] * m2.data[1][1];
        fin.data[1][0] = m1.data[1][0] * m2.data[0][0] + m1.data[1][1] * m2.data[1][0];
        fin.data[1][1] = m1.data[1][0] * m2.data[0][1] + m1.data[1][1] * m2.data[1][1];
        return fin;
    }

    // M的n次幂:使用快速幂算法,提高计算速度
    static M mPower(M m, long n) {
        M E = new M();
        E.data[0][0] = 1;
        E.data[1][1] = 1;
        while (n != 0) {
            if ((n & 1) == 1) {
                E = mul(E, m);
            }
            m = mul(m, m);
            n >>= 1;
        }
        return E;
    }

    // 使用矩阵求解求解斐波那契数列
    static long fib(long i) {
        M A = new M();
        A.data[0][0] = 1;
        A.data[0][1] = 1;
        M B = new M();
        B.data[0][0] = 1;
        B.data[0][1] = 1;
        B.data[1][0] = 1;
        M ans = mul(A, mPower(B, i - 2));
        return ans.data[0][0];
    }
    // 使用矩阵快速幂:40分
        static void solve2() {
            /*
             * for(int i=3;i<=10;i++) { System.out.println(fib(i)); }
             */
            long a = 1, b = 1;
            if (m >= n + 2) {
                b = fib(n + 2);
                // b就是n+2项
                System.out.println(b % p - 1);
            } else {
                System.out.println(fib(n + 2) % fib(m) % p - 1);
            }
        }
    static long mm(long a,long b,long mod) {
        if(a>b) {
            long t=b;
            b=a;
            a=t;
        }
        long x=0;
        while(b!=0) {
            if((b&1)==1)
                x=(x+a)%mod;
            a=(a*2)%mod;
            b>>=1;
        }
        return x;
    }
    // 将两个2*2的矩阵相乘
    static M mul(M m1, M m2, long mod) {
        M fin = new M();
        fin.data[0][0] = mm(m1.data[0][0] ,m2.data[0][0],mod) + mm(m1.data[0][1] , m2.data[1][0],mod);
        fin.data[0][1] = mm(m1.data[0][0] ,m2.data[0][1],mod) + mm(m1.data[0][1] , m2.data[1][1],mod);
        fin.data[1][0] = mm(m1.data[1][0] ,m2.data[0][0],mod) + mm(m1.data[1][1] , m2.data[1][0],mod);
        fin.data[1][1] = mm(m1.data[1][0] ,m2.data[0][1],mod) + mm(m1.data[1][1] , m2.data[1][1],mod);
        return fin;
    }
    
    // M的n次幂:使用快速幂算法,提高计算速度,同时解决数据太大问题
    static M mPower(M m, long n, long mod) {
        M E = new M();
        E.data[0][0] = 1;
        E.data[1][1] = 1;
        while (n != 0) {
            if ((n & 1) == 1) {
                E = mul(E, m, mod);
            }
            m = mul(m, m, mod);
            n >>= 1;
        }
        return E;
    }

    // 使用矩阵求解求解斐波那契数列的同时解决数据太大超出long型数据
    static long fib(long i, long mod) {
        M A = new M();
        A.data[0][0] = 1;
        A.data[0][1] = 1;
        M B = new M();
        B.data[0][0] = 1;
        B.data[0][1] = 1;
        B.data[1][0] = 1;
        M ans = mul(A, mPower(B, i - 2,mod), mod);
        return (ans.data[0][0])%mod;
    }

    

    // 使用矩阵快速幂以及将mod同时带进去:60分
    static void solve3() {
        
//       for(int i=3;i<=10;i++) { System.out.println(fib(i)); }
         
        if (m >= n + 2) {
            System.out.println(fib(n + 2, p)%p - 1);
        } else {
            long fibm = fib(m);// 这里无法再次优化了，只能硬算
            /*
             * System.out.println(fib(m)); System.out.println(fib(n+2,fibm));
             */
            System.out.println((fib(n + 2, fibm) %fibm)% p - 1);
        }
    }
    // 使用矩阵快速幂以及将mod同时带进去同时添加mm函数进一步缩短时间: 100分
        static void solve4() {
            
//           for(int i=3;i<=10;i++) { System.out.println(fib(i)); }
             
            if (m >= n + 2) {
                System.out.println(fib(n + 2, p)%p - 1);
            } else {
                long fibm = fib(m);// 这里无法再次优化了，只能硬算
                /*
                 * System.out.println(fib(m)); System.out.println(fib(n+2,fibm));
                 */
                System.out.println((fib(n + 2, fibm) %fibm)% p - 1);
            }
        }
    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner cin = new Scanner(System.in);
        n = cin.nextLong();
        m = cin.nextLong();
        p = cin.nextLong();
        solve4();
    }

}

蓝桥杯-斐波那契

原文：https://www.cnblogs.com/GarrettWale/p/12504612.html