マトリックス高速べき乗(テンプレート)

            1 1

                    1 0

/*    
 Matrix A;
    A.clear();
    /* */
    A.n = A.m = 2;
    A.a[0][0] = 1;
    A.a[0][1] = 1;
    A.a[1][0] = 1;
    A.a[1][1] = 0;

  ：Matrix res = Matrix_pow(A, n - 1);
cout<
#include 

typedef long long ll;
using namespace std;
/* */
const int maxn = 5;
const int maxm = 5;
const int mod = 10000;
struct Matrix
{
    int n, m;
    ll a[maxn][maxm];
    void clear()
    {
        n = m = 0;
        memset(a, 0, sizeof(a));
    }
    Matrix operator * (const Matrix &b) const
    {
        Matrix tmp;
        tmp.clear();
        tmp.n = n;
        tmp.m = b.m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
            {
                if (!a[i][j]) continue;  //        
                for (int k = 0; k < b.m; k++)
                {
                    tmp.a[i][k] += a[i][j] * b.a[j][k];
                    tmp.a[i][k] %= mod;
                }
            }
        return tmp;
    }
};
int n;
Matrix Matrix_pow(Matrix A, int k)
{
    Matrix res;
    res.clear();
    res.n = res.m = 2;// 
    for (int i = 0; i < 2; i++) // 
        res.a[i][i] = 1;
    while(k)
    {
        if (k & 1) res = res * A;
        k >>= 1;
        A = A * A;
    }
    return res;
}
int main ()
{

    //freopen("text.in","r",stdin);
    Matrix A;
    A.clear();
    /* */
    A.n = A.m = 2;
    A.a[0][0] = 1;
    A.a[0][1] = 1;
    A.a[1][0] = 1;
    A.a[1][1] = 0;
    while(1)
    {
        int n;
        scanf("%d", &n);
        if(n == -1)
            break;
        if(n == 0)
        {
            printf("0
");
            continue;
        }
        Matrix res = Matrix_pow(A, n - 1);
        printf("%lld
", res.a[0][0]);
    }
    return 0;
}