[原创]玲珑OJ 1109 Niro plays with snow [递推+预处理矩阵乘法]【数学】

# include <bits/stdc++.h>

using namespace std;

typedef long long int LL;

# define abs(x) ((x)>0?(x):-(x))

const int MOD =  1234321237;
const int N   =  1e5+7 ;
const int M   =  8 ;
/********************************************/

struct Matrix{
    LL m[M][M];
    void clearO(){
        for(int i=0; i<M; i++) //初始化矩阵
            for(int j=0; j<M; j++)
                m[i][j]= 0;
    }
    void clearE(){
        for(int i=0; i<M; i++) //初始化矩阵
            for(int j=0; j<M; j++)
                m[i][j]= (i==j);
    }
    void display(){
        for(int i=0; i<M; i++){
            for(int j=0; j<M; j++)
                printf("%d ",m[i][j]);
            puts("");
        }
        puts("-----");
    }
};

Matrix operator * (Matrix &a,Matrix &b){
    Matrix c;
    c.clearO();

    for(int k=0; k<M; k++)
        for(int i=0; i<M; i++){ //实现矩阵乘法
            if(a.m[i][k] <= 0)  continue;
            for(int j=0; j<M; j++){
                if(b.m[k][j] <= 0)    continue;
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j]+MOD)%MOD;
            }
        }
    return c;
}

Matrix operator ^ (Matrix &a,LL b){
    Matrix c;
    c.clearE();
    while(b){
        if(b&1) c= c * a ;
        b >>= 1;
        a = a * a ;
    }
    return c;
}

Matrix a[100];
void init(){

    a[0].m[0][1]=6;
    a[0].m[1][1]=3,a[0].m[1][2]=2,a[0].m[1][4]=1;
    a[0].m[2][1]=1,a[0].m[2][2]=2,a[0].m[2][3]=1,a[0].m[2][4]=2;
    a[0].m[3][1]=0,a[0].m[3][2]=0,a[0].m[3][3]=3,a[0].m[3][4]=3;
    a[0].m[4][5]=6;
    a[0].m[5][5]=3,a[0].m[5][6]=2;
    a[0].m[6][5]=1,a[0].m[6][6]=2,a[0].m[6][7]=1;
    a[0].m[7][5]=0,a[0].m[7][6]=0,a[0].m[7][7]=3;

    for(int i=1;(1ll<<i)<=1e18;i++)    a[i]=a[i-1]*a[i-1];
}

int main(){
    init();

    int _;
    Matrix b,c,d;
    LL n ;

    scanf("%d",&_);
    for(int i=1;i<=_;i++){
        scanf("%lld",&n);n--;

        b.clearO();
        b.m[0][0]=1;

//        b.display();

        for(int i=0;(1ll<<i)<=n;i++){
            if(n&(1ll<<i)){
                for(int j=0;j<M;j++){
                    for(int k=0;k<M;k++){
                        b.m[1][j]=(b.m[1][j]+b.m[0][k]*a[i].m[k][j]+MOD)%MOD;
                    }
                }
                for(int j=0;j<M;j++){
                    b.m[0][j]=b.m[1][j];
                    b.m[1][j]=0;
                }
            }
        }

        printf("%lld " ,((b.m[0][0]+b.m[0][1])%MOD+(b.m[0][2]+b.m[0][3])%MOD)%MOD);
        printf("%lld\n",((b.m[0][4]+b.m[0][5])%MOD+(b.m[0][6]+b.m[0][7])%MOD)%MOD);
    }


    return 0;
}