题意：给定一个矩阵的第0列的第1到n个数，第一行第1个数开始每个数分别为233， 2333........，求第n行的第m个数。
分析：
其实也没那么难，自己想了半天还没往对的方向想，m最大1e9，应该立即想到要用到快速幂，关键在于递推矩阵。
递推矩阵的作用是依次算出每一列，第1列第一个数233是前一列的23*10+3，将前一列增加一个元素[3, 23, a1, a2,....an]，然后第一列第一个数为3，对应向量[1, 0, 0, 0.....0],233对应向量[1, 10, 0, .....0]，下一个的数对应[1, 10, 1.....0]， 接下来每个数对应的向量是上一个数的向量最后一个1元素后面增加1个1，这样将n+2个向量构成一个(n+2)*(n+2)的矩阵，需要求m次该矩阵，然后和[3, 23, a1, a2, .....an]相乘。
代码：
#include <cstdio>
#include <iostream>
#include <vector>
#include <algorithm>
#define inf 0x0f0f0f0f
#define pb push_back
#define bug(x) printf("line %d: >>>>>>>>>>>>>>>\n", (x));
#define in freopen("F:\\code\\data\\data.txt", "r", stdin);
#define out freopen("F:\\code\\data\\data_out.txt", "w", stdout); #define SZ(x) ((int)x.size())
#define lson rt<<1, l, m
#define rson rt<<1|1, m+1, r
using namespace std; typedef long long LL;
const int maxn = ;
const int M = ; struct Matrix
{
int n, m;
LL a[maxn][maxn];
Matrix(int n, int m)
{
this->n = n;
this->m = m;
for(int i = ; i < maxn; i++)
for(int j = ; j < maxn; j++)
a[i][j] = ;
}
Matrix operator * (const Matrix &o)const
{
Matrix c(n, o.m);
for(int i = ; i < n; i++)
for(int j = ; j < o.m; j++)
{
for(int k = ; k < m; k++)
c.a[i][j] = (c.a[i][j]+a[i][k]*o.a[k][j]%M)%M;
}
return c;
}
};
int n, m;
int main()
{ while(scanf("%d%d", &n, &m) == )
{
Matrix f(n+, n+), res(n+, n+), tmp(n+, );
tmp.a[][] = ;
tmp.a[][] = ;
for(int i = ; i <= n+; i++)
scanf("%I64d", &tmp.a[i][]);
for(int i = ; i <= n+; i++)
for(int j = ; j <= n+; j++)
{
if(i == )
{
f.a[i][] = ;
break;
}
else if(i == )
{
f.a[i][] = ;
f.a[i][] = ;
break;
}
else
{
if(j < i)
f.a[i][j] = f.a[i-][j];
else if(j == i) f.a[i][j] = ;
}
}
for(int i = ; i < n+; i++)
for(int j = ; j < n+; j++)
if(i == j)
res.a[i][j] = ;
while(m)
{
if(m&)
res = res*f;
f = f*f;
m >>= ;
}
tmp = res*tmp;
printf("%I64d\n", tmp.a[n+][]);
}
return ;
}