矩阵快速幂

矩阵快速幂

快速幂可以将o(n)的复杂度降为o(logn)

原理如下:

任何一个整数均可以用二进制来表示。

当我们要求x^n时,

可以先将n表示为2^k1+2^k2+2^k3.......

那么x^n=x^(2^k1) * x^(2^k2) * x^(2^k3)......

举个例子:22=10110

那么x^22=x^16 * x^4 * x^2;

下面是代码

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
mat quickpow(ll x,ll n,ll mod)
{
	ll res=1;
	while(n)
	{
		if(n&1) res=res*x%mod;//如果二进制最低位为1,则乘上x^(2^i)
		x=x*x%mod;
		n>>=1;
	}
	return res;
}

同理,我们也可以做到矩阵快速幂,只需将算术乘法换成矩阵乘法即可。

矩阵快速幂常常用于加速递推公式

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<bits/stdc++.h>
#define ll long long
#define MAX_N 100
using namespace std;
struct mat
{
	ll a[MAX_N][MAX_N];
}; 
mat mul(mat A,mat B,int mod)
{	mat C;
	for(int i=0;i<N;i++)
		for(int j=0;j<N;j++)
		{
			C.a[i][j]=0;
			for(int k=0;k<N;k++)
			C.a[i][j]+=(A.a[i][k]*B.a[k][j])%mod;
		}
	return C;
}
mat mpow(mat A,int n)
{
	mat c;
	memset(c.a,0,sizeof(c.a));
	for(int i=0;i<N;i++)
	c.a[i][i]=1;
	while(n)
	{
		if(n&1) c=mul(c,A);
		A=mul(A,A);
		n>>=1;
	}
	return c;
}