原题链接：
题意简述：给定矩阵每个元素计算公式，求下标为（m，m）的元素的值。
解题思路：刚开始想着递推求出整个矩阵，后来我哭了。m 可达1e9，要化简到 lg 级别才能不超时，这时我隐约想到用转移矩阵加快速幂做了，根据《算法竞赛进阶指南》P151页所述，如果一类问题具有如下特点：
- 可以抽象出一个长度为n的一维向量，该向量在每个单位时间发生一次变化
- 变化的形式是一个线性递推（只有若干“加法”或者“乘一个系数”的运算）
- 该递推式在每个时间可能作用于不同的数据上，但本身保持不变
- 向量变化时间（即递推的轮数）很长，但向量长度n不大。
那么就可以考虑采用矩阵乘法进行优化。具体步骤就是构造出转移矩阵、状态矩阵，通过对转移矩阵的快速幂来加速递推。时间复杂度为(n^3 lgT)，其中T为递推轮数。
代码示例（如何构造转移矩阵于状态矩阵就不写了，手太冷了，而且我也讲不好）：
#include#include const int maxn = 50;const int M = 10000007;struct Matrix{ int n; int v[maxn][maxn]; Matrix(int n){ this->n = n; memset(v,0,sizeof v); } Matrix operator *(const Matrix &b) const{ Matrix C(n); for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) for(int k = 0;k < n;k++) C.v[i][j] = (C.v[i][j] + 1ll*v[i][k]*b.v[k][j]%M) % M; return C; } Matrix operator +(const Matrix &b) const{ Matrix C(n); for(int i = 0;i < n;i++) for(int j = 0;j < n;j++) C.v[i][j] = (v[i][j] + b.v[i][j])%M; return C; } void qpow(int k){ Matrix E(n); Matrix A = *this; for(int i = 0;i < n;i++) E.v[i][i] = 1; while(k){ if(k&1) E = E*A; A = A*A; k >>= 1; } *this = E; }};int main(){ int n,m; while(scanf("%d%d",&n,&m) != EOF){ Matrix tran(n+2); for(int i = 0;i <= n;i++){ tran.v[i][0] = 10; tran.v[i][n+1] = 1; } for(int i = 1;i <= n;i++) for(int j = 1;j <= i;j++) tran.v[i][j] = 1; tran.v[n+1][n+1] = 1; tran.qpow(m); int t[n+2],ans[n+2]; memset(ans,0,sizeof ans); t[0] = 23,t[n+1] = 3; for(int i = 1;i <= n;i++) scanf("%d",&t[i]); for(int i = 0;i < n+2;i++) for(int j = 0;j < n+2;j++) ans[i] = (ans[i] + 1ll*tran.v[i][j]*t[j]%M)%M; printf("%d\n",ans[n]); } }