学步园

不解释

#define N 10
int MOD ;

struct Mat{
    int mat[10][10];
};
//初始化单位矩阵
Mat init(){
    Mat E;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(i == j)
            E.mat[i][i] = 1;
            else
            E.mat[i][j] = 0;
        }
    }
    return E;
}
//重载乘法
Mat operator *(Mat a,Mat b){
    Mat c;
    memset(c.mat,0,sizeof(Mat));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            for(int k = 0; k < N; k++){
                if(a.mat[i][k] && b.mat[k][j]){
                    c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j]) % MOD;
                }
            }
        }
    }
    return c;
}
//重载加法
Mat operator +(Mat a,Mat b){
    Mat c;
    memset(c.mat,0,sizeof(Mat));
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            c.mat[i][j] = (a.mat[i][j] + b.mat[i][j]) % MOD;
        }
    }
    return c;
}
//重载幂次方
Mat operator ^(Mat A,LL x){
    if(x == 1)return A;
    Mat c;
    c = init();
    for(; x ; x >>= 1){
        if(x&1){
            c = c*A;
        }
        A = A*A;
    }
    return c;
}
int main(){
    int k,m;
    while(scanf("%d%d",&k,&m)!=EOF){
        if(k<10){
            printf("%d\n",k % m);
        }else{
            int a[10];
            int i;
            for(i=0;i<10;i++)scanf("%d",&a[i]);
            Mat gao = { a[0],a[1],a[2],a[3],a[4],a[5],a[6],a[7],a[8],a[9],
                        1,0,0,0,0,0,0,0,0,0,
                        0,1,0,0,0,0,0,0,0,0,
                        0,0,1,0,0,0,0,0,0,0,
                        0,0,0,1,0,0,0,0,0,0,
                        0,0,0,0,1,0,0,0,0,0,
                        0,0,0,0,0,1,0,0,0,0,
                        0,0,0,0,0,0,1,0,0,0,
                        0,0,0,0,0,0,0,1,0,0,
                        0,0,0,0,0,0,0,0,1,0 };
            MOD = m;
            Mat ans = gao^(k-9);
            int sum = 0;
            for(i = 0;i < 10;i++){
                sum += ans.mat[0][i]*(9-i);
            }
            printf("%d\n",sum%MOD);
        }
    }
    return 0;
}