学步园

这题太狠了 ，TLE的我难受，整整做了一天。。

借用别人的图片，就是这样构造矩阵。。。  其中 X = 2 * a2 ， Y= -1；

code：

#include <cstdio>
#include <cstring>
#include <iostream>

#define LL __int64
using namespace std;


LL a2,n,M;

struct Matrix
{
    LL mat[5][5];
}A,E,T;

Matrix operator * (const Matrix a,const Matrix b)
{
    Matrix res;
    int i,j,k;
    for(i=1;i<=4;i++)
    {
        for(j=1;j<=4;j++)
        {
            res.mat[i][j] = 0;
            for(k=1;k<=4;k++)
            {
                if (a.mat[i][k] && b.mat[k][j])
                    res.mat[i][j] = (res.mat[i][j] + a.mat[i][k]*b.mat[k][j] )%M;
            }
        }
    }
    return res;
}

Matrix operator ^ (const Matrix a,LL exp)
{
    Matrix tmp=a;
    Matrix res=E;
    while(exp)
    {
        if(exp & 1)
            res = res *tmp;
        exp >>= 1;
        tmp = tmp * tmp;
    }
    return res;
}

void init()
{
    A.mat[1][3]= A.mat[1][4] = A.mat[2][1] = 0;
    A.mat[3][1] = A.mat[3][3] = A.mat[3][4] = 0;
    A.mat[4][1] = A.mat[4][3] = 0;
    A.mat[1][1] = A.mat[1][2] = A.mat[3][2] = A.mat[2][3] = 1;
    A.mat[2][2] = (4 * a2 * a2)%M;
    A.mat[2][4] = ((-4 * a2)%M + M) %M;
    A.mat[4][2] = (2 * a2)%M;
    A.mat[4][4] = M - 1;
    T.mat[2][1] = (a2*a2)%M;
    T.mat[4][1] = a2%M;
}

int main()
{
    memset(T.mat,0,sizeof(T.mat));
    memset(E.mat,0,sizeof(E.mat));
    E.mat[1][1] = E.mat[2][2] = E.mat[3][3] = E.mat[4][4] = 1;
    T.mat[1][1] = T.mat[3][1] = 1;
    LL res;
    Matrix ans;
    int cas;
    scanf("%d",&cas);
    while(cas--)
    {
        scanf("%I64d%I64d%I64d",&a2,&n,&M);
        init();
        ans = A ^ (n-1);
        ans = ans * T;
//        for(int i=1;i<=4;i++)
//        {
//            for(int j=1;j<=4;j++)
//                printf("%I64d ",ans.mat[i][j]);
//            puts("");
//        }
        printf("%I64d\n",ans.mat[1][1]);
    }
	return 0;
}