思路与算法

令 $Q=\begin{pmatrix}1&1\\1&0\end{pmatrix}$，列状态满足 $(F_{i+1},F_i)^\mathsf T=Q(F_i,F_{i-1})^\mathsf T$。从 $(F_1,F_0)=(1,0)$ 出发，$Q^n$ 的第1行第2列为 $F_n$（对 $n=0$，单位矩阵该位置为0）。对每个输入的 $n$ 用二进制快速幂求 $Q^n\bmod10000$，输出这个元素。

本题固定模数10000，一次读一个 $n$，直到-1终止；与只读一组 $n,m$ 的题不同。每轮查询重新初始化单位矩阵和底矩阵。指数为0时不进入幂循环，直接得到 $F_0=0$。

正确性说明

矩阵转移第一行相加给出斐波那契下一项，第二行复制当前项。由初始条件归纳，矩阵幂包含相邻斐波那契数；取非对角元素得到 $F_n$，零次幂也与 $F_0$ 一致。快速幂保持结果矩阵与剩余底矩阵幂的乘积等于目标幂，按二进制位乘入并平方保持不变式，最终得到 $Q^n$。加乘中取模保留余数，每次查询独立初始化，所以每行输出正确。

复杂度

矩阵维度固定为2，初始化为常数，一次矩阵乘法为常数操作。设各次查询指数为 $n_q$，含读入和初始化的总时间为 $O(Q+\sum_q\log(n_q+1))$，额外空间为 $O(1)$；逐次处理，不存全部查询。

易错点

1. 0是合法查询，-1才是终止标志；终止行不输出。
2. 求 $Q^n$ 的非对角元，不要误用求 $F_n$ 的另一种 $Q^{n-1}$ 写法而让 $n=0$ 产生负指数。
3. 每次查询重置矩阵，重复输入仍逐行输出。
4. 输出普通余数，不要求补前导零。乘法采用64位并每次取模。
5. 覆盖 $n=0,1,10^9$、多次0、重复项以及仅终止标志。独立答案用快速倍增，并与0至500的直接递推核对。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct Mat {
    ll a[2][2]{};
};
Mat multiply(const Mat &x, const Mat &y) {
    Mat c;
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int k = 0; k < 2; k++)
                c.a[i][j] = (c.a[i][j] + x.a[i][k] * y.a[k][j]) % 10000;
    return c;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    ll n;
    while (cin >> n && n != -1) {
        Mat result, base;
        result.a[0][0] = result.a[1][1] = 1;
        base.a[0][0] = base.a[0][1] = base.a[1][0] = 1;
        while (n) {
            if (n & 1)
                result = multiply(result, base);
            base = multiply(base, base);
            n >>= 1;
        }
        cout << result.a[0][1] << '\n';
    }
}