有一\(n\times m\)的矩阵\(\{a\}\)，定义\(a[0][0]=0,a[0][1]=233,a[0][2]=2333,a[0][3]=23333...\),然后给出\(a[1][0],a[2][0],...,a[n][0]\),未给出或定义的位置满足\(a[i][j]=a[i-1][j]+a[i][j-1]\),询问\(a[n][m]\)的值\(mod\ 10000007\)，\(n ≤ 10,m ≤ 10^9\)。

解

显然对于第0行，我们有转移方程\(a[0][i]=a[0][i-1]\times 10+3\)，这个是可以转移的，显然需要增添辅助1，注意到n很小，故考虑整个压维，故设状态矩阵（以n=2为例）

\[\begin{bmatrix}1&a[0][i]&a[1][i-1]&a[2][i-1]\end{bmatrix}\]

不难得知转移方程

\[\begin{bmatrix}1&3&0&0\\0&10&1&1\\0&0&1&1\\0&0&0&1\end{bmatrix}\]

于是根据规律，填写转移矩阵和状态矩阵即可。

参考代码：

#include 
    
     #include 
     
      #include 
      
       #define il inline#define ri register#define ll long long#define yyb 10000007using namespace std;struct matrix{    ll jz[12][12];    il void clear(){        memset(jz,0,sizeof(jz));    }    il void unit(){        clear();ri int i;        for(i=0;i<12;++i)jz[i][i]=1;    }    il void print(){        ri int i,j;        for(i=0;i<12;++i,putchar('\n'))            for(j=0;j<12;++j)                printf("%lld ",jz[i][j]);        putchar('\n');    }    il matrix operator*(matrix x){        matrix y;y.clear();        ri int i,j,k;        for(i=0;i<12;++i)            for(j=0;j<12;y.jz[i][j]%=yyb,++j)                for(k=0;k<12;++k)                    y.jz[i][j]+=jz[i][k]*x.jz[k][j]%yyb;        return y;    }template
       
            il matrix operator^(free y){        matrix ans,x(*this);ans.unit();        while(y){            if(y&1)ans=ans*x;            x=x*x,y>>=1;        }return ans;    }}tran,state;int main(){    ll n,m;int i,j;    while(scanf("%lld%lld",&n,&m)!=EOF){        state.jz[0][0]=1,state.jz[0][1]=233;        for(i=2;i<=n+1;++i)scanf("%lld",&state.jz[0][i]);        tran.jz[0][0]=1,tran.jz[0][1]=3,tran.jz[1][1]=10;        for(i=2;i<=n+1;++i)            for(j=1;j<=i;++j)                tran.jz[j][i]=1;        state=state*(tran^m);        printf("%lld\n",state.jz[0][n+1]);        tran.clear(),state.clear();    }    return 0;}