自动搬运

查看原文

来自洛谷，原作者为

	ask_silently 凡王之血，必以剑终

搬运于2025-08-24 22:58:38，当前版本为作者最后更新于2024-07-26 16:29:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原题传送门

矩阵快速幂

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

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

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

我们再次发现，对于第 $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;
}

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