矩阵第一题。也是矩阵的模板题。下面是模板。

比较重要的是，矩阵的乘法会有很多很神奇的用法。比如如下几个网站所讲。

   这是Matrix67大神的网站。

 

#include <iostream>

using namespace std;

#define MAXN 2

#define LL long long

#define mod 10000

class Matrix

{

public:

    long long m[MAXN][MAXN];

    //二维数组存放矩阵 

    Matrix(){}

    //对数组的初始化 

    void init(long long  num[MAXN][MAXN]){

        for (int i = 0; i < MAXN; i++){

            for (int j = 0; j < MAXN; j++){

                m[i][j] = num[i][j];

            }

        }

    }

    //重载矩阵的乘法运算 

    friend Matrix operator*(Matrix &m1, Matrix &m2) {

        int i, j, k;

        Matrix temp;

        for (i = 0; i < MAXN; i++) {

            for (j = 0; j < MAXN; j++) {

                temp.m[i][j] = 0;

                for (k = 0; k < MAXN; k++)

                    temp.m[i][j] += (m1.m[i][k] * m2.m[k][j])%mod;

                temp.m[i][j] %= mod;

                //注意每一步都进行取模 

            }

        }

        return temp;

    }

    //矩阵的快速幂 

    friend Matrix quickpow(Matrix &M, long long n){

        Matrix tempans;

        //初始化为单位矩阵 

        //初始化 

        for (int i = 0; i < MAXN; i++){

            for (int j = 0; j < MAXN; j++){

                if (i == j)

                    tempans.m[i][j] = 1;

                else

                    tempans.m[i][j] = 0;

            }

        }

        //快速幂（类似整数） 

        while (n)

        {

            if (n & 1)

                tempans = tempans * M;

            //已经重载了* 

            n = n >> 1;

            M = M * M;

        }

        return tempans;

    }

};

int main()

{

    LL n;

    while (cin >> n &&n != -1)

    {

        Matrix M;

        LL mm[MAXN][MAXN] = { 1, 1, 1, 0 };

        M.init(mm);

        Matrix temp = quickpow(M, n);

        cout << temp.m[1][0] << endl;

    }

}