矩阵快速幂非详解

2019-11-14 08:43:50

字体：大中小

来源：转载

供稿：网友

#include <cstdio>#include <cstring>int n, k;const int mod = 9973;struct matrix{ int tr[10][10]; matrix Operator * (const matrix &a) const{//重载运算符 matrix tmp; memset(tmp.tr, 0, sizeof(tmp.tr)); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++){ for(int k = 0; k < n; k++) tmp.tr[i][j] += tr[i][k] * a.tr[k][j]; tmp.tr[i][j] %= mod;//这里要取模，不然可能溢出 } return tmp; }}ans, ori;matrix pow_mod(int k){ for(int i = 0; i < n; i++) ans.tr[i][i] = 1;//化为单位矩阵 while(k){ if(k&1) ans = ans*ori;//不能写成ans *= ori，因为没有重载*=运算符 k >>= 1; ori = ori*ori; }//核心代码，下面有解释}int main(){ int t; scanf("%d", &t); while(t--){ scanf("%d%d", &n, &k); memset(ans.tr, 0, sizeof(ans.tr)); memset(ori.tr, 0, sizeof(ori.tr)); for(int i = 0; i < n; i++) for(int j = 0; j < n; j++) scanf("%d", &ori.tr[i][j]); pow_mod(k); long long res = 0; for(int i = 0; i < n; i++){ res += ans.tr[i][i] % mod; } PRintf("%lld/n", res % mod); } return 0;}

核心代码：

while(k){ if(k&1) ans = ans*ori; k >>= 1; ori = ori*ori; }

假设 k = 89，其二进制为 1011001，显然 a^k = ( a^1 ) * ( a^8 ) * ( a^16 ) * ( a^64 ); 也就是，k的二进制位为0时，可以跳过（右移）。

每次判断k的最后一位二进制位，若为1，则 ans = ans*ori ，然后k右移一位，ori 乘以本身。

上一篇：LeetCode 70. Climbing Stairs

下一篇：51Nod 1049 最大子段和（DP