(Relax 矩阵快速幂1.1)POJ 3070 Fibonacci(求第n个斐波那契数的后四位。n很大)

题意：求第n个斐波那契数。

思路：矩阵快速幂。利用，可化为矩阵快速幂，即：由于矩阵乘法具有结合律，因此对于矩阵A，有A^4 = A * A * A * A = (A*A) * (A*A) = A^2 * A^2。我们可以得到这样的结论：当n为偶数时，A^n = A^(n/2) * A^(n/2)；当n为奇数时，A^n = A^(n/2) * A^(n/2) * A （其中n/2取整）。

#include   
#include   
  
using namespace std;  
  
  
const int M = 10000;  
  
struct Matrix {  
    int v[3][3];  
} m;  
  
Matrix mtMul(Matrix A, Matrix B)     //  求矩阵 A * B  
        {  
    Matrix C;  
    C.v[0][0] = (A.v[0][0] * B.v[0][0] + A.v[0][1] * B.v[1][0]) % M;  
    C.v[0][1] = (A.v[0][0] * B.v[0][1] + A.v[0][1] * B.v[1][1]) % M;  
    C.v[1][0] = (A.v[1][0] * B.v[0][0] + A.v[1][1] * B.v[1][0]) % M;  
    C.v[1][1] = (A.v[1][0] * B.v[0][1] + A.v[1][1] * B.v[1][1]) % M;  
    return C;  
}  
  
Matrix mtPow(Matrix A, int k)        //  求矩阵 A ^ k  
        {  
    if (k == 1)  
        return A;  
    A = mtPow(A, k / 2);  
    if (k % 2 == 0) {  
        return mtMul(A, A);  
    } else {  
        return mtMul(mtMul(A, A), m);  
    }  
}  
  
int main(){  
    int n;  
    m.v[0][0] = 0,m.v[0][1] = 1;  
    m.v[1][0] = 1,m.v[1][1] = 1;  
  
    while(scanf("%d",&n)!=EOF,n != -1){  
        if(n == 0){  
            printf("0\n");  
            continue;  
        }  
  
        Matrix A = mtPow(m,n);  
  
        printf("%d\n",A.v[0][1]);  
    }  
  
    return 0;  
}