题解：P10503 233 Matrix

· · 题解

原题传送门

矩阵快速幂

我们观察一下题目，看见了 n,m 的范围，又看到了矩阵，一眼矩阵快速幂【手动自信】

那如何推状态转移方程呢？

我们发现每一行相邻两个数的关系不太好看出来，于是我们看一看每一列相邻两个数的关系。

233
a 233+a
b 233+a+b
c 233+a+b+c

我们再次发现，对于第 i 行的数，都等于前一列在此行前面包括此行的数与本列最上方数的和，于是状态转移方程呼之欲出，但只是欲出。

注意到 233 转移到下一列 2333 需要乘上 10 再加上 3，由于该数在第一行，所以会影响到下面所有的数，所以该列所有的数都需要再加上 3，于是，我们就可以推出状态转移方程了：

\begin{bmatrix}1&1&1&1&\cdots&1\\0&10&10&10&\cdots&10&\\0&0&1&1&\cdots&1\\0&0&0&1&\cdots&1\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots\\0&0&0&0&\cdots&1\end{bmatrix}

初始矩阵：

\begin{bmatrix}3&23&a_1&a_2&\cdots&a_n\end{bmatrix}

ACcode

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N=15;
const int mod=1e7+7;

int n,m;
int a[N];

struct node{
    int x,y;
    int ju[N][N];
}chu,cheng,sum;

inline int read(){
    int t=0,f=1;
    register char c=getchar();
    while (c<48||c>57) f=(c=='-')?(-1):(f),c=getchar();
    while (c>=48&&c<=57)t=(t<<1)+(t<<3)+(c^48),c=getchar();
    return f*t;
}

void init(){
    memset(chu.ju,0,sizeof(chu.ju));
    memset(cheng.ju,0,sizeof(cheng.ju));
    memset(sum.ju,0,sizeof(sum.ju));
    chu.x=1,chu.y=n+2;
    chu.ju[1][1]=3,chu.ju[1][2]=23;
    for(int i=3;i<=n+2;i++) chu.ju[1][i]=a[i-2];
    cheng.x=cheng.y=n+2;
    cheng.ju[1][1]=1;
    for(int i=2;i<=n+2;i++){
        cheng.ju[1][i]=1,cheng.ju[2][i]=10;
        for(int j=3;j<=i;j++) cheng.ju[j][i]=1;
    }
    sum.x=sum.y=n+2;
    for(int i=1;i<=n+2;i++) sum.ju[i][i]=1;
}

node operator *(const node &x,const node &y){
    node z;
    memset(z.ju,0,sizeof(z.ju));
    z.x=x.x,z.y=y.y;
    for(int i=1;i<=z.x;i++){
        for(int j=1;j<=z.y;j++){
            for(int k=1;k<=x.y;k++) z.ju[i][j]=(z.ju[i][j]+(x.ju[i][k]*y.ju[k][j])%mod)%mod;
        }
    }
    return z;
}

int ksm(int b){
    while(b){
        if(b&1) sum=sum*cheng;
        cheng=cheng*cheng;
        b>>=1;
    }
    sum=chu*sum;
    return sum.ju[1][n+2];
}

signed main(){
    while(cin>>n>>m){
        for(int i=1;i<=n;i++) a[i]=read();
        init();
        cout<<ksm(m)<<"\n";
    }
    return 0;
}

完结，撒花【花】【花】【花】