二十七 205. 斐波那契 (矩阵乘法|快速幂)

205. 斐波那契 (矩阵乘法|快速幂)

对矩阵和矩阵快速幂的讲解

import java.util.*;

public class Main {
    private static final int mod = 10000;
    
    private static int[][] mul(int[][] a, int[][] b) {
        int[][] c = {{0, 0}, {0, 0}};
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                for (int k = 0; k < 2; k++) {
                    c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
                }
            }
        }
        return c;
    }
    
    private static int fib(int n) {
        int[][] a= {{0, 1}, {0, 0}};
        int[][] f= {{0, 1}, {1, 1}};
        while (n != 0) {
            if ((n & 1) != 0) {
                a = mul(a, f);
            }
            f = mul(f, f);
            n >>= 1;
        }
        return a[0][0];
    }
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        while (n != -1) {
            System.out.println(fib(n));
            n = sc.nextInt();
        }
    }
}