算法

$O(logn)$

斐波那契数列可以用矩阵来表示。
$a_n = a_{n - 1} + a_{n - 2}$
$a_{n - 1} = a_{n - 1}$
所以矩阵就是{1， 1}，{1， 0}。可以采用矩阵快速幂，类比于整数的快速幂来求这个矩阵。

代码

blablabla
import java.util.Scanner;

class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int n;
        while ((n = in.nextInt()) != -1) {
            System.out.println(fib(n));
        }
        in.close();
    }

    private static int fib(int n) {
        if (n == 0) return 0;
        int[][] A = new int[][]{{1, 1}, {1, 0}};
        int[][] ret = new int[][]{{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = mul(ret, A);
            }
            A = mul(A, A);
            n >>= 1;
        }
        return ret[1][0];
    }

    private static int[][] mul(int[][] A, int[][] B) {
        int n = A.length;
        int[][] ans = new int[n][n];
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                for (int k = 0; k < n; ++k) {
                    ans[i][j] += A[i][k] * B[k][j];
                }
                ans[i][j] %= 10000;
            }
        }
        return ans;
    }
}