UVA 10518 How Many Calls?

题意：一个递推式第n项%b是多少。

递推式：

构造矩阵：

#include<cstdio>

#include<cstring>

#include<cmath>

#include<vector>

#include<algorithm>

using namespace std;

long long MOD;

long long n;

struct Matrix

{

    long long A[][];

    int R, C;

    Matrix operator*(Matrix b);

};

Matrix X, Y, Z;

Matrix Matrix::operator*(Matrix b)

{

    Matrix c;

    memset(c.A, , sizeof(c.A));

    int i, j, k;

    for (i = ; i <= R; i++)

    for (j = ; j <= b.C; j++)

    for (k = ; k <= C; k++)

        c.A[i][j] = (c.A[i][j] + (A[i][k] * b.A[k][j]) % MOD) % MOD;

    c.R = R; c.C = b.C;

    return c;

}

void init()

{

    memset(X.A, , sizeof X.A);

    memset(Y.A, , sizeof Y.A);

    memset(Z.A, , sizeof Z.A);

    Z.R = ; Z.C = ;

    Z.A[][] = Z.A[][] = Z.A[][] = ;

    X.R = ; X.C = ;

    X.A[][] = ; X.A[][] = ; X.A[][] = ;

    X.A[][] = ; X.A[][] = ; X.A[][] = ;

    X.A[][] = ; X.A[][] = ; X.A[][] = ;

    Y.R =; Y.C = ;

    for (int i = ; i <= ; i++) Y.A[i][i] = ;

}

void work()

{

    while (n)

    {

        if (n %  == ) Y = Y*X;

        n = n >> ;

        X = X*X;

    }

    Z = Z*Y;

    printf("%lld\n", Z.A[][]);

}

int main()

{

    int Case = ;

    while (~scanf("%lld%lld", &n, &MOD))

    {

        if (!n&&!MOD) break;

        init();

        printf("Case %d: %lld %lld ", Case++, n, MOD);

        work();

    }

    return ;

}