题源：Problem - 5015 (hdu.edu.cn)
题意
给出第一行的规律 a00，a01,a02, , , , a0m = 0,233,2333,23333 ,,,,
第一列的数input给出 a00, a10, a20 , a30, ,,, an0 = 0, a1,a2 ,a3,a4,,,,an
第 aij 为 ai-1，j + ai, j-1 , 求 an,m项
规律总结
把矩阵看作一列一列的找规律
可以发现第 j 列 可以很容易通过第 j-1 列 相加推导得出， 除去第一行有些不对称
第一行分别为 0，233，2333，23333 ，可以将第一个改为23，则 ai= ai-1*10 +3 。
一般快速幂
当计算 a ^n 时，例如 12345 ^255 ，需要进行 255次乘法，时间复杂度 O(n)
可以将时间复杂度降到 O(log n )
方法是 255 = 111111112
可以将 12345^255 = 12345 ^(2^7*1+2^6*1+ 2*5*1+ + 2^0*1)
= 12345^(2^7) * 12345* (2^6)* *** 12345^(2^0)
时间复杂度降为项为1的个数和最高次幂的位数 ，8^7 时间复杂度 O(log n*log n）
给出算法
int QuickPower(int a,int n){ //return a^n int ret = 1; int tem = a; while(n){ if(n&1) ret *= tem; tem *= tem; n>>=1; } return ret; }
矩阵快速幕
将乘法变成矩阵乘法，给出模板。
给出算法模板：
const int N = 100; struct Mat { int m[N][N]; } ans, res; //res result Mat Mul(Mat a, Mat b,int n){ //定义矩阵的乘法 Mat ret; for (int i = 0; i < n;i++) for (int j = 0; j < n; j++) ret.m[i][j] = 0; for (int i = 0; i < n;i++) for (int j = 0; j < n;j++) for (int k = 0; k < n;k++) ret.m[i][j] += a.m[i][k] * b.m[k][j]; return ret; } void QuickPower(int N,int n){ // 求 n阶方阵 的 N次幂 for (int i = 0; i < n;i++) for (int j = 0; j < n;j++) ans.m[i][j] = 0; while(N){ if(N&1) ans = Mul(ans, res,n); N >>= 1; res = Mul(res, res,n); } }