本文共 1854 字，大约阅读时间需要 6 分钟。
题意：第一行给出了 233 2333 23333 233333 ......
也给出了第一列的数 ，让你计算 第n行m列的值 a[i][j] = a[i-1][j] + a[i][j-1] ;
题解：我们要先预处理行，然后对列进行快速幂，这样就可以很快计算出结果；
/** 本题是一个n * m的矩阵(m比较大) a[0][1] = 233 2333 a[1][0] a[1][1] a[2][0] a[2][1] a[3][0] a[3][1] a[4][0] a[4][1] . . . . { 10 0 0 0 1 } . { 1 1 0 0 0 } {2333,a[1][1],a[2][1],a[3][1],.....,3} = { 1 1 1 0 0 }*（{233,a[1][0],a[2][0],a[3][0],.....,3} 的转置矩阵） { 1 1 1 1 0 } { 0 0 0 0 1 }**/#include #include #include #include using namespace std;#define mod 10000007typedef __int64 LL;LL a[20];int n,m;struct Z{ LL m[13][13];}ret,p;void init(){ memset(ret.m,0,sizeof(ret.m)); memset(p.m,0,sizeof(p.m)); for(int i = 0;i <= n+1;i++) ret.m[i][i] = 1; p.m[0][0] = 10;p.m[0][n+1] = 1; for(int i = 1;i <= n;i++) for(int j = 0;j <= i;j++) p.m[i][j] = 1; p.m[n+1][n+1] = 1;}Z operator * (Z a,Z b){ Z c; memset(c.m,0,sizeof(c.m)); for(int i = 0;i <= n + 1;i++) for(int k = 0;k <= n + 1;k++) if(a.m[i][k]) for(int j = 0;j <= n + 1;j++) c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j]) % mod; return c;}Z Pow(int k){ init(); while(k){ if(k&1) ret = ret * p; p = p * p; k >>= 1; } return ret;}int main(){ while(cin >> n >> m) { Z r; memset(a,0,sizeof(a)); a[0] = 233; for(int i = 1;i <= n;i++) cin >> a[i]; a[n+1] = 3; r = Pow(m); LL ans = 0; for(int i = 0;i <= n+1;i++) ans = (ans + r.m[n][i] * a[i] )% mod; cout << ans << endl; }} 转载地址：http://edsgi.baihongyu.com/