剑指 Offer 10- II. 青蛙跳台阶问题使用矩阵快速幂时取余的问题(C++)

77 阅读 0 评论 51 点赞

我是靠谱客的博主勤恳灯泡，这篇文章主要介绍剑指 Offer 10- II. 青蛙跳台阶问题使用矩阵快速幂时取余的问题(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
32
33
34
35
36
37
38
39
40
41
42
43
44
/*
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。
求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
*/
class Solution {
public:
	int MOD = int(1e9 + 7);
	int numWays(int n) { 
		if (n < 2)
		{
			return 1;
		}
		vector<vector<long>> M = { {1,1}, {1,0} };
		vector<vector<long>> ret = pow(M, n-1);
		return (ret[0][0]+ ret[0][1]) % MOD;
	}

	vector<vector<long>> pow(vector<vector<long>>&M, int n)
	{
		vector<vector<long>> ret = { {1,0},{0,1} };
		while (n > 0) {
			if (n & 1) {
				ret = Multiply(ret, M) ;
			}
			n >>= 1;
			M = Multiply(M, M);
		}
		return ret;
	}

	vector<vector<long>> Multiply(vector<vector<long>>& a, vector<vector<long>>& b)
	{
		vector< vector<long>> c = { {0,0},{0,0} };
		for (int i = 0; i < 2; i++)
		{
			for (int j = 0; j < 2; j++)
			{
				c[i][j] = (a[i][0] * b[0][j] + a[i][1] * b[1][j])  ;
				c[i][j] = c[i][j] % MOD;
			}
		}
		return c;
	}
};