1.知识储备

快速幂原理

当b为偶数时，a ^ b = (a ^ (b/2) ) * (a ^ (b/2) )

当b为奇数时，a ^ b = (a ^ (b/2) ) * (a ^ (b/2) ) * a

这个不难理解，举个例子

3 ^ 6 = (3 ^ 3 ) * (3 ^ 3) 此时b=6为偶数

3 ^ 5 = (3 ^ 2 ) * (3 ^ 2) * 3 此时b=5为奇数

根据这两个等式，当我们在算a ^ b时可以先算出 a ^ (b / 2)，然后再求a ^ b，减少了重复的b / 2次计算，因此时间复杂度是O(log N)

模运算法则之一

a # b % c = ( a % c # b %c ) % c 其中 # 代表运算加、减、乘。

2.递归写法

1
2
3
4
5
6
7
8
9
typedef long long LL;
//计算(a^b)%mod;
LL pow1(LL a, int b, int mod) //递归写法
{
	if (b == 0)return 1;
	LL t = pow1(a, b / 2, mod) % mod; //先求a ^ (b/2)
	if (b & 1)return t * t% mod * a% mod; //如果为奇数，需要额外乘上a
	else return t * t% mod;
}

3.迭代写法

1
2
3
4
5
6
7
8
9
10
11
12
//计算(a^b)%mod;
LL pow2(LL a, int b, int mod) //迭代写法
{
	LL ans = 1;
	while (b) {
		if (b & 1) //判断b的奇偶性
			ans = ans * a % mod; //如果为奇数，需要额外乘上a
		a = a * a % mod;
		b >>= 1; //除以2
	}
	return ans;
}

4.矩阵快速幂

image-20201001193120357

三重循环求矩阵乘法，一个乘法就三重循环就O(n3)，别说求幂了

1
2
3
4
5
6
7
8
9
10
int[][N] mul(int a[][N],int b[][N],int n)//n是矩阵大小，n<N
{
    int c[N][N];
    memset(c,0,sizeof(c));
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            for(int k=1;k<=n;k++)
                c[i][j]+=a[i][k]*b[k][j];
	return c;
}

矩阵快速幂和普通快速幂的思想是一样的，只是运算的对象不同，把数的相乘换成矩阵的相乘而已。

具体代码如下：

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
#include<cstdio>
#include<cstring>
typedef long long ll;
const int mod = 1e9 + 5;
const int MAXN = 10005;//矩阵的大小
struct Mat {
	ll m[MAXN][MAXN];
}ans;//ans为结果矩阵

//把数的相乘转换为矩阵相乘
Mat Mul(Mat a, Mat b, int n) {//计算矩阵a乘矩阵b，n为矩阵的大小
	Mat c;//临时矩阵c
	memset(c.m, 0, sizeof(c.m));
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int k = 1; k <= n; k++)
				c.m[i][j] = (c.m[i][j] + (a.m[i][k] * b.m[k][j]) % mod) % mod;
	return c;
}
//本质的快速幂思想是一样的
Mat power(Mat a, int b, int n) {//计算a^b，n为矩阵的大小
	for (int i = 1; i <= n; i++)//构造单位矩阵
		ans.m[i][i] = 1;
	while (b) {
		if (b & 1)
			ans = Mul(ans, a, n);
		a = Mul(a, a, n);
		b >>= 1;
	}
	return ans;
}

矩阵快速幂思想是不难，难的是如何构造矩阵来解决求递推式的问题

这里留个学习的链接，再来道例题

附上一道整了我3个多小时的题目，记录下，第一次做矩阵快速幂，吐血，没想到输入的n也要long long !!!。

原题

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
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<cstdio>
#include<cstring>
typedef long long ll;
const int mod = 99999999;
const int MAXN = 7;//矩阵的大小
struct Mat {
	ll m[MAXN][MAXN];
}ans,initM;//ans为结果矩阵,initM为初始化矩阵
void init()
{
	initM.m[0][1] = 1, initM.m[0][4] = 2, initM.m[0][6] = 5;
	initM.m[1][0] = 1, initM.m[1][4] = 3, initM.m[1][5] = 2,initM.m[1][6] = 3;
	initM.m[2][0] = 1;
	initM.m[3][1] = 1;
	initM.m[4][2] = 1;
	initM.m[5][3] = 1;
	initM.m[6][6] = 1;
}


Mat Mul(Mat a, Mat b) {
	Mat c;//临时矩阵c
	memset(c.m, 0, sizeof(c.m));
	for (int i = 0; i < MAXN; i++)
		for (int j = 0; j < MAXN; j++)
			for (int k = 0; k < MAXN; k++)
				c.m[i][j] = (c.m[i][j] + (a.m[i][k] * b.m[k][j]) % mod) % mod;
	return c;
}
Mat power(Mat a, ll b) {
	for (int i = 0; i < MAXN; i++)//构造单位矩阵
		ans.m[i][i] = 1;
	while (b) {
		if (b & 1)
			ans = Mul(ans, a);
		a = Mul(a, a);
		b >>= 1;
	}
	return ans;
}
void PrintAns(Mat ans)
{
	int t[] = { 6,5,1,4,2,3,1 };
	ll nums[2] = { 0,0 };
	for (int k = 0; k < 2; k++)
			for (int i = 0; i < 7; i++)
				nums[k] = (nums[k] + (ans.m[k][i] * t[i]) % mod) % mod;
	//for (int k = 0; k < 2; k++)
	//	nums[k] = (ans.m[k][0] * 6 % mod + ans.m[k][1] * 5 % mod +
	//		ans.m[k][2] * 1 % mod + ans.m[k][3] * 4 % mod +
	//		ans.m[k][4] * 2 % mod + ans.m[k][5] * 3 % mod + ans.m[k][6] * 1 % mod) % mod;
	printf("%lld\n%lld\n", nums[0], nums[1]);
}

int main()
{
	ll n;
	scanf("%lld", &n);
	if (n == 1) {
		printf("2\n3\n");
	}
	else if (n == 2) {
		printf("1\n4\n");
	}
	else if (n == 3) {
		printf("6\n5\n");
	}
	else {
		init();
		ans = power(initM,n-3);
		PrintAns(ans);
	}
	return 0;
}