极限的斐波那契问题 TODO

斐波那契问题本身是一个经典问题，算法多种多样。这个题目的本身就是某种斐波那契的变形。

极限的时间复杂度

最佳复杂度$O(logn)O(logn)$

极限的空间复杂度

最佳复杂度$O(1)O(1)$

奇怪的模运算

import java.util.*;
public class Main{


    static final int MOD = 1000000007;
    static int[][] cal;
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        for (int i = 0;i<n;i++){
            int A = sc.nextInt();
            int B = sc.nextInt();
            int m = sc.nextInt();
            System.out.println(fib(A,B,m));
        }
        
    }
    public static long fib(int A, int B, int n) {
        if (n == 0) return 2;
        if (n == 1) return A;

        int[][] q = {{A, -B}, {1, 0}};
        int[][] res = pow(q, n - 1);

        return ((long)res[0][0]*A + (long)res[0][1]*2+(long)MOD)%MOD;
    }

    public static int[][] pow(int[][] a, int n) {
        //int[][] ret = {{1, 0}, {0, 1}};
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }

    public static  int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = (int) (((long) a[i][0] * b[0][j] + (long) a[i][1] * b[1][j]+(long)MOD) % MOD);
                c[i][j] = (c[i][j]+MOD) % MOD;
            }
        }
        return c;
    }
}