快速幂

前言

有两种思想,但代码一样,指数折半或者利用二进制,即从十进制和二进制两种方向理解

两种方法求解过程,以2的11次为例

指数折半2.11

= 2 * 4^5
=2 * 4 * 8 ^ 2
=2 * 4 * 16

二进制2^11,1011嘛

=2 * 4 * 16

指数折半

核心思想就是每一步都把指数分成两半，而相应的底数做平方运算

3^10=(3 * 3) ^ 5

3^10=9 ^ 5

现在我们的问题是如何把指数5变成原来的一半，5是一个奇数，5的一半是2.5，但是我们知道，指数不能为小数，因此我们不能这么简单粗暴的直接执行5/2，然而，这里还有另一种方法能表示9^5

9^5=（ 9^4 ）*（ 9^1 ）

long long quick_power(int base, int power)
{
	long long ans = 1;
	while (power > 0)           //指数大于0进行指数折半，底数变其平方的操作
	{
		if (power & 1)     //指数为奇数
		{
			power -= 1;         //指数减一,不写也可以int自动取整
			ans *= base % mod;     //分离出当前项并累乘
		}
		power >>= 1;         //指数折半
		base *= base % mod;       //底数变其平方
	}
	return ans % mod;
}

二进制

比如n的11次,把11用二进制拆分,8+0+2+1,即1011.

从低位开始递推,1次1次等于2次,2次2次等于4次……

不过代码本质也是在做底数翻倍,比如2 ^ 1到2 ^ 2就是2 ^ 1到4 ^ 1,和指数折半是一样的

long long quick_power(int base, int power)
{
    long long ans = 1;   //用于存储项累乘与返回最终结果，由于要存储累乘所以要初始化为1
    while (power > 0)           //指数大于0说明指数的二进制位并没有被左移舍弃完毕
    {
        if (power & 1){          //当前位为1
            ans *= base % mod;     //累乘当前项并存储
        }
        power >>= 1;            //指数位右移(区别主要就在这一步的理解上)
        base *= base % mod;           //递推,如n的2次变为n的4次
    }
    return ans % mod;
}

矩阵快速幂

矩阵乘法

矩阵乘法

m x n的矩阵A乘以n x u的矩阵B得到m x u的矩阵C

公式=
$$
C[ i ] [ j ] = \sum_{k=1}^{n}A[i] [k] * B[k] [j]
$$

for(int i = 1; i <= m; i++){
    for(int j = 1; j <= u; j++){
        for(int k = 1; k <= n; k++){
            c[i][j] += a[i][k] * b[k][j];
        }
    }
}

快速幂实现

贴个矩阵快速幂代码

题目洛谷p3390

https://www.luogu.com.cn/problem/P3390

vector<vector<int>>func(vector<vector<int>>& a, vector<vector<int>>& b){
	vector<vector<int>>c(N, vector<int>(N, 0));
	for(int i = 0; i < N; i++){
		for(int j = 0; j < N; j++){
			for(int k = 0; k < N; k++){
				c[i][j] += a[i][k]*b[k][j];
			}
		}
	}
	return c;
} 

vector<vector<int>>quick_power(vector<vector<int>>& base, int power){
	vector<vector<int>>ans(N, vector<int>(N, 0));
	for(int i = 0; i < N; i++) ans[i][i] = 1;
	while(power){
		if(power & 1) ans = func(base, ans);
		base = func(base, base);
		power >>= 1;
	}
	return ans;
}

加速递推

洛谷p1939

https://www.luogu.com.cn/problem/P1939