矩阵快速幂的模板（C++）

迷南。 2023-03-06 03:50 41阅读 0赞

顾名思义，快速幂就是快速计算某个数的n次幂。其时间复杂度为 O(log₂N)， 与朴素的O(N)相比效率有了极大的提高。  
  前面学习了整数的快速幂：比如我们要求12^11，我们其实可以求12 ^ (2 ^ 0+2 ^ 1+2 ^ 3)  
整数快速幂代码：

ll fastpow(ll x,ll y) {    //求取x^y 
    	ll res=1;
    	while(y) { 
    		if(y%2==1) { //为奇数，当前最低位为1，res就要乘以当前位置的权重 
    			res*=x;
    		}
    		x*=x;   //每右移一次，最低位的权重都要乘以x 
    		y/=2;   //右移 
    	}
    	return res;
    }

矩阵的快速幂是一样的，只不过**答案矩阵的初始状态不再是一个1，而是一个单位矩阵**：因为单位矩阵在矩阵中的作用等同于整数中的1。  
  因此矩阵快速幂的思路就很简单了：我们先定义好矩阵的乘法，其它跟整数的快速幂一毛一样。

定义矩阵：

struct matrix { 
    	ll mat[6][6];
    	init() { 
    		memset(mat, 0, sizeof(mat));
    	}
    };

这里矩阵的维度可以自己定义两个整型变量来存储。

定义矩阵乘法：

matrix mul(matrix a,matrix b) {    //return a*b
    	matrix c;
    	c.init();
    	for(int i = 0;i < 6;i++) { 
    		for(int j = 0;j < 6;j++) { 
    			for(int k = 0;k < 6;k++) { 
    				c.mat[i][j] += ((a.mat[i][k] % mod) * (b.mat[k][j] % mod)) % mod;
    				c.mat[i][j] %= mod;
    			}
    		}
    	}
    	return c;
    }

定义矩阵快速幂：

matrix fast_pow(matrix A, int n) {    //return A^n%mod
    	matrix B;
    	B.init();
    	for(int i = 0;i < 6;i++) {    //单位矩阵 
    		B.mat[i][i] = 1;
    	}
    	while(n) { 
    		if(n & 1) { 
    			B = mul(B, A);
    		}
    		A = mul(A, A);
    		n >>= 1; 
    	}
    	return B;
    }

可以看到的确跟整数的快速幂是一样的。