矩阵快速幂详解

快速幂

利用二进制的方式来进行实现

\(2^0 = 2^0\)

\(2^1 = 2^1\)

\(2^2 = 2^2\)

\(2^3 = 2^2 * 2\)

\(2^4 = 2^4\)

\(2^5 = 2^4 * 2\)

\(2^6 = 2^4 * 2^2\)

\(2^7 = 2^4 * 2^2 * 2\)

所以我们可以看出来的是

二进制位上我们现在只有当某一位是１的时候才乘

举个例子

所以原来\(O(b)\)复杂度一下降低到了\(O(logb)\)

inline int pow(int a,int b)
{
    int r=1,base=a;
    while(b)
    {
        if(b&1) r*=base;//如果当前位是1，那么直接相乘
        base*=base;//不管是什么数字下一位都需要再乘一次(2的倍数)
        b>>=1;//移到下一位
    }
    return r;//返回结果
}

矩阵乘法

定义矩阵乘法的运算方式是:

举个例子

int n;//矩阵大小

void Up(int &x, int y) { x = (x + y) % mod; }//简单定义 += 

struct Matrix
{
	int a[n][n];//矩阵
	friend Matrix operator *(const Matrix x, const Matrix y)//定义矩阵类型的乘法
	{
		Matrix c;//定义新的矩阵用来存储结果
		memset(c.a, 0, sizeof(c.a));//初始化
		for(int i = 0; i < n;i ++)//进行枚举
			for(int j = 0; j < n;j ++)
				for(int k = 0; k < n;k ++)
					Up(c.a[i][j], x.a[i][k] * y.a[k][j] % mod);//相乘 
		return c;//返回答案矩阵
	}
};

如何利用矩阵乘法计算

在计算递推式的时候，我们可以把递推式构建成矩阵乘法的样子

比如形如下列递推式的递推式:

我们可以考虑构造成:

然后就有:

然后构造起来的道理是这样，但是真正的矩阵是什么样子的还得自己知道怎么推然后再去做

假如给你一个形如\(f(n) = a * f(n - 1) + b * f(n - 2) + c * f(n - 3)\)你要是不会推还是会GG的

然后因为有的时候\(dp\)的递推式也可以用矩阵来加速，所以用处很大

矩阵乘法快速幂

前一部分的模板

void Up(int &x, int y) { x = (x + y) % mod; }//简单定义+=

struct Matrix
{
	int a[n][n];
	friend Matrix operator *(const Matrix x, const Matrix y)//定义矩阵乘法
	{
		Matrix c;
		memset(c.a, 0, sizeof(c.a));
		for(int i = 0; i < n; i ++)
			for(int j = 0; j < n; j ++)
				for(int k = 0; k < n; k ++)
					Up(c.a[i][j], x.a[i][k] * y.a[k][j] % mod); 
		return c;
	}
};

Matrix Qpow(Matrix x, int timer)//矩阵快速幂
{
	Matrix base;//定义结果矩阵
	for(int i = 0; i < n; i ++)
		for(int j = 0; j < n; j ++)
			base.a[i][j] = 0;
	for(int i = 0; i < n; i ++) base.a[i][i] = 1;
	for(; timer; timer >>= 1, x = x * x)
		if(timer & 1) base = base * x;
	return base;
}

PROB

• Luogu P1962 斐波那契数列

矩阵快速幂详解

原文：https://www.cnblogs.com/eqvpkbz/p/12984834.html