Problem Statement

Given a non-negative integer n where 0 ≤ n ≤ 2×10^9, compute the n-th term of the Fibonacci sequence modulo 10000. The sequence is defined as F(0) = 0, F(1) = 1, and F(n) = F(n-1) + F(n-2) for n > 1. The input consists of multiple test cases, each containing a single integer n. Processing terminates when n = -1.

Algorithmic Analysis

Limitations of Conventional Methods

A straightforward iterative or recursive approach requires O(n) time complexity. With n reaching two billion, this results in approximately 2×10^9 operations per test case, which easily exceeds standard execution limits. Alternatively, Binet's closed-form formula involves irrational numbers (√5), making it unsuitable for modular arithmetic without resorting to cumbersome high-precision floating-point calculations.

Matrix Formulation

Linear recurrences can be efficiently modeled using matrix multiplication. The Fibonacci relation depends on the two preceding terms, allowing us to construct a state vecter and a transition matrix:

[F(n-1), F(n)] × [[0, 1], [1, 1]] = [F(n), F(n+1)]

By applying this transformation repeatedly, we derive a direct formula for the n-th term:

[F(n), F(n+1)] = [F(0), F(1)] × [[0, 1], [1, 1]]^n = [0, 1] × T^n

where T represents the constant transition matrix. This shifts the problem from linear iteration to computing the n-th power of a matrix.

Binary Exponentiation

Matrix multiplication is associative, which enables the use of binary exponantiation (also known as exponentiation by squaring). This technique reduces the number of matrix multiplications from O(n) to O(log n). For n = 2×10^9, log₂(n) is rough 31, making the computation nearly instantaneous. Each 2×2 matrix multiplication involves a constant number of arithmetic operations, keeping the overall complexity well within limits.

Implementation Details

To streamline the implementation, the initial 1×2 state vector [0, 1] can be padded into a 2×2 matrix by appending a row of zeros: [[0, 1], [0, 0]]. This allows a single matrix multiplication routine to handle both the state updates and the transition matrix squaring, eliminating the need for separate vector-matrix functions. The final result will consistently reside at index [0][0] of the resulting matrix.

The following C++ implementation applies modular arithmetic at each addition and multiplication step to prevent integer overflow and satisfy the problem constraints.

#include <iostream>
#include <cstring>

constexpr int MOD_VAL = 10000;

// Computes dest = lhs * rhs under modulo arithmetic
void multiply_matrices(int dest[2][2], int lhs[2][2], int rhs[2][2]) {
    int temp[2][2] = {{0, 0}, {0, 0}};
    for (int row = 0; row < 2; ++row) {
        for (int col = 0; col < 2; ++col) {
            for (int k = 0; k < 2; ++k) {
                temp[row][col] = (temp[row][col] + lhs[row][k] * rhs[k][col]) % MOD_VAL;
            }
        }
    }
    std::memcpy(dest, temp, sizeof(temp));
}

int solve_fibonacci(int n) {
    // Padded initial state matrix representing [F(0), F(1)]
    int state[2][2] = {{0, 1}, {0, 0}};
    // Transition matrix T
    int trans[2][2] = {{0, 1}, {1, 1}};

    int exponent = n;
    while (exponent > 0) {
        if (exponent & 1) {
            multiply_matrices(state, state, trans);
        }
        multiply_matrices(trans, trans, trans);
        exponent >>= 1;
    }
    return state[0][0];
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    while (std::cin >> n && n != -1) {
        std::cout << solve_fibonacci(n) << '\n';
    }
    return 0;
}

The algorithm processes each test case in O(log n) time with O(1) auxiliary space. Intermediate modulo operations guarantee that all matrix elements stay within standard 32-bit integer bounds, completely removing the dependency on arbitrary-precision libraries.