题解 | #斐波那契数列#

import java.util.Arrays;

public class Solution {
    public static int Fibonacci(int n) {
        int[][] m = new int[][] {{1, 1}, {1, 0}};
        int[][] res = pow(m, n - 1);
        return res[0][0];
    }

    public static int[][] pow(int[][] a, int n) {
        int aRow = a.length;
        int aCol = a[0].length;
        int[][] res = new int[aRow][aCol];
        for (int i = 0; i < aRow; i++) {
            Arrays.fill(res[i], 0);
            res[i][i] = 1;
        }
        while (n > 0) {
            if (n % 2 == 1) {
                res = mul(res, a);
            }
            a = mul(a, a);
            n /= 2;
        }
        return res;
    }

    public static int[][] mul(int[][] a, int[][] b) {
        int aRow = a.length;
        int aCol = a[0].length;
        int bRow = b.length;
        int bCol = b[0].length;
        if (aCol != bRow) {
            return new int[][] {};
        }
        int[][] res = new int[aRow][bCol];
        for (int i = 0; i < aRow; i++) {
            for (int j = 0; j < bCol; j++) {
                int sum = 0;
                for (int k = 0; k < aCol; k++) {
                    sum += a[i][k] * b[k][j];
                }
                res[i][j] = sum;
            }
        }
        return res;
    }
}