题意：给定一个矩阵的第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]相乘。
代码：
1 #include <cstdio> 2 #include <iostream> 3 #include <vector> 4 #include <algorithm> 5 #define inf 0x0f0f0f0f 6 #define pb push_back 7 #define bug(x) printf("line %d: >>>>>>>>>>>>>>> ", (x)); 8 #define in freopen("F:\code\data\data.txt", "r", stdin); 9 #define out freopen("F:\code\data\data_out.txt", "w", stdout); 10 11 #define SZ(x) ((int)x.size()) 12 #define lson rt<<1, l, m 13 #define rson rt<<1|1, m+1, r 14 using namespace std; 15 16 typedef long long LL; 17 const int maxn = 22; 18 const int M = 10000007; 19 20 struct Matrix 21 { 22 int n, m; 23 LL a[maxn][maxn]; 24 Matrix(int n, int m) 25 { 26 this->n = n; 27 this->m = m; 28 for(int i = 0; i < maxn; i++) 29 for(int j = 0; j < maxn; j++) 30 a[i][j] = 0; 31 } 32 Matrix operator * (const Matrix &o)const 33 { 34 Matrix c(n, o.m); 35 for(int i = 0; i < n; i++) 36 for(int j = 0; j < o.m; j++) 37 { 38 for(int k = 0; k < m; k++) 39 c.a[i][j] = (c.a[i][j]+a[i][k]*o.a[k][j]%M)%M; 40 } 41 return c; 42 } 43 }; 44 int n, m; 45 int main() 46 { 47 48 while(scanf("%d%d", &n, &m) == 2) 49 { 50 Matrix f(n+2, n+2), res(n+2, n+2), tmp(n+2, 1); 51 tmp.a[0][0] = 3; 52 tmp.a[1][0] = 23; 53 for(int i = 2; i <= n+1; i++) 54 scanf("%I64d", &tmp.a[i][0]); 55 for(int i = 0; i <= n+1; i++) 56 for(int j = 0; j <= n+1; j++) 57 { 58 if(i == 0) 59 { 60 f.a[i][0] = 1; 61 break; 62 } 63 else if(i == 1) 64 { 65 f.a[i][0] = 1; 66 f.a[i][1] = 10; 67 break; 68 } 69 else 70 { 71 if(j < i) 72 f.a[i][j] = f.a[i-1][j]; 73 else if(j == i) f.a[i][j] = 1; 74 } 75 } 76 for(int i = 0; i < n+2; i++) 77 for(int j = 0; j < n+2; j++) 78 if(i == j) 79 res.a[i][j] = 1; 80 while(m) 81 { 82 if(m&1) 83 res = res*f; 84 f = f*f; 85 m >>= 1; 86 } 87 tmp = res*tmp; 88 printf("%I64d ", tmp.a[n+1][0]); 89 } 90 return 0; 91 }