A Simple Math Problem

/*题意：给你题目描述的函数，然后让你求f(k)%m的值初步思路：简单的爆一下#错误:超内存！#改进思路：    想一下这个式子的实质，不用递归写，用循环写，但是需要循环1e9次，肯定是不可行的,可以用矩阵相乘f(x)是从0，1，2...9乘上a0,a1,a2...    .a9递推过来的这样就能得出来一个矩阵，线性代数还没学，矩阵真的有点麻烦，构造矩阵的时候老是想错了。#再次错误：矩阵相乘虽然可以解决空间问题，但是没法解决时间问题；这里真的有点糊涂了，常数都有快速幂，矩阵的快速幂怎么就没有想起来呐！*/#include<bits/stdc++.h>#define ll long longusing namespace std;ll m,k;struct Matrix{    ll m[12][12];    void init0(){//构造用来乘的矩阵(相当于“幺元”吧，随便想到了离散中的概念就这么叫吧)        memset(m,0,sizeof m);        for(int i=1;i<10;i++)            m[i][i-1]=1;    }    void init1(){//构造最初的a0~a9        memset(m,0,sizeof m);        for(int i=0;i<10;i++){            m[i][0]=9-i;        }    }};Matrix Mul_Matrix(Matrix a,Matrix b){    Matrix c;    c.init0();    for(int i=0;i<10;i++){         for(int j=0;j<10;j++){            c.m[i][j]=0;            for(int k=0;k<10;k++){                c.m[i][j]+=(a.m[i][k]*b.m[k][j])%m;            }            c.m[i][j]%=m;        }    }    return c;}/**************矩阵快速幂*********************/Matrix Pow(Matrix a,Matrix b,int x){    while(x){        if(x&1){            b=Mul_Matrix(a,b);        }        a=Mul_Matrix(a,a);        x>>=1;    }    return b;}/**************矩阵快速幂*********************/Matrix a,b;int main(){    //freopen("in.txt","r",stdin);    while(scanf("%lld%lld",&k,&m)!=EOF){        a.init0();        b.init1();        //cout<<k<<" "<<m<<endl;        for(int i=0;i<10;i++) scanf("%lld",&a.m[0][i]);        // for(int i=9;i<k;i++){            // b=Mul_Matrix(a,b);            // for(int i=0;i<10;i++){                // for(int j=0;j<10;j++)                    // cout<<a.m[i][j]<<" ";                // cout<<"         ";                // for(int j=0;j<10;j++)                    // cout<<b.m[i][j]<<" ";                // cout<<endl;            // }        // }        Matrix c=Pow(a,b,k-9);//利用矩阵快速幂        printf("%lld\n",c.m[0][0]);    }    return 0;}