Time Limit: 1000MS

　　Memory Limit: 65536K

　　In the Fibonacci integer sequence, F0 = 0, F1 = 1, and Fn = Fn − 1 + Fn − 2 for n ≥ 2. For example, the first ten terms of the Fibonacci sequence are:

　　0, 1, 1, 2, 3, 5, 8, 13, 21, 34, …

　　An alternative formula for the Fibonacci sequence is

　　.

　　Given an integer n, your goal is to compute the last 4 digits of Fn.

　　The input test file will contain multiple test cases. Each test case consists of a single line containing n (where 0 ≤ n ≤ 1,000,000,000). The end-of-file is denoted by a single line containing the number −1.

　　For each test case, print the last four digits of Fn. If the last four digits of Fn are all zeros, print ‘0’; otherwise, omit any leading zeros (i.e., print Fn mod 10000).

　　0

　　9

　　999999999

　　1000000000

　　-1

　　0

　　34

　　626

　　6875

　　As a reminder, matrix multiplication is associative, and the product of two 2 × 2 matrices is given by

　　.

　　Also, note that raising any 2 × 2 matrix to the 0th power gives the identity matrix:

　　.

　　lz的第一道矩阵快速幂。

　　之前lz只知道快速幂，没想到还有矩阵快速幂。

　　那在这里就先稍微讲一下快速幂。

　　比如求x^11

　　11的二进制是1011，我们都知道(X^m)*(X^n) = X^(m+n)。所以同样我们也可以将x^11这样来做。（x^11 = x^8*x^2*x^1 = x^(8+2+1)）

　　求x^n还有一种求法就是二分递归来求。利用x^n = x^(n/2)*x^(n/2) （n为偶数时），x^n = x^(n/2)*x^(n/2)*x（n为奇数时）；

　　具体实现如下

　　这里再说一下

　　单位矩阵的定义： n*n的矩阵 Matrix ( i , i )=1; 任何一个矩阵乘以单位矩阵就是它本身 n*单位矩阵=n， 可以把单位矩阵等价为整数1。（单位矩阵用在矩阵快速幂中）

　　好，稍微了解一下后进人正题。

　　题意：求斐波那契数列的第n项%10000。

　　因为数据较大，而且题里给出了斐波那契的矩阵公式

　　这不就是求这个矩阵A（假设为A）的n次嘛。所以Fn就可以通过A^n来求出。

　　好，接下来上AC code（^_^）