思想直接迁自快速幂,不难懂,矩阵的乘法学过线性代数都没什么大问题,无非用到了operator *比较新鲜而已。
矩阵快速幂的关键点在于构建矩阵。 简单举几个例子:
斐波那契数列:f[n] = f[n - 1] + f[n - 2] 则可有 [f[n - 2], f[n - 1]] * A = [f[n], f[n - 1]] 求得 A = [ 0 1 1 1 ] A = \left[ \begin{matrix} 0 & 1\\ 1 & 1 \end{matrix} \right] A=[0111](现场瞎编的)数列:f[n] = f[n - 1] + 2 * f[n - 2] + 3 * f[n - 3] [f[n - 1], f[n - 2], f[n - 3]] * A = [f[n], f[n - 1], f[n - 2] 求得 A = [ 1 1 0 2 0 1 3 0 0 ] A = \left[ \begin{matrix} 1 &1 &0\\ 2 &0 &1\\ 3 &0 &0 \end{matrix} \right] A=⎣⎡123100010⎦⎤ #define MAT_SIZE 3 struct mat { int m[110][110];}a, w; mat operator *(mat &a, mat &b) { mat c; memset(c.mat, 0, sizeof c.mat); for(int i = 0; i < MAT_SIZE; ++i) for(int j = 0; j < MAT_SIZE; ++j) for(int k = 0; k < MAT_SIZE; ++k) c.mat[i][j] = (c.mat[i][j] + a.mat[i][k] * b.mat[k][j] % mod) % mod; return c; } mat power(mat a, ll b, int n){ //计算a^b,n为矩阵的大小 mat ans; for(int i = 1; i <= n ; i++) ans.m[i][i] = 1; while(b){ if(b & 1) ans = ans * a; a = a * a; b >>= 1; } return ans; }