3070.斐波拉契数列--快速幂

import java.util.Scanner;
public class Main {
    public static int quick_pow(int a[][], int b, int mod) {
        int temp[][] = { { 1, 0 }, { 0, 1 } };
        while (b > 0) {
            if (b % 2 == 1)
                temp = mul(a, temp, mod);
            a = mul(a, a, mod);
            b = b >> 1;
        }
        return temp[0][0];
    }
    public static int[][] mul(int a[][], int b[][], int mod) {
        int res[][] = new int[a[0].length][b.length];
        for (int i = 0; i < a.length; i++) {
            for (int j = 0; j < b[0].length; j++) {
                res[i][j] = 0;
                for (int k = 0; k < a[0].length; k++) {
                    res[i][j] += (a[i][k] % mod) * (b[k][j] % mod) ;
                }
                res[i][j] %= mod;
            }
        }
        return res;
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()) {
            int n = sc.nextInt();
            if (n == -1) {
                return;
            } else if (n == 0) {
                System.out.println(0);
            } else if (n == 1) {
                System.out.println(1);
            } else {
                int a[][] = { { 1, 1 }, { 1, 0 } };
                System.out.println(quick_pow(a, n - 1, 10000));// 这里要减1 因为从F2开始
            }
    }
}}