蓝桥杯奇异的虫群矩阵快速幂

问题描述

　　在一个奇怪的星球上驻扎着两个虫群A和B，它们用奇怪的方式繁殖着，在t+1时刻A虫群的数量等于t时刻A虫群和B虫群数量之和，t+1时刻B虫群的数量等于t时刻A虫群的数量。由于星际空间的时间维度很广阔，所以t可能很大。OverMind 想知道在t时刻A虫群的数量对 p = 1,000,000,007.取余数的结果。当t=1时 A种群和B种群的数量均为1。

输入格式

　　测试数据包含一个整数t，代表繁殖的时间。

输出格式

　　输出一行，包含一个整数，表示对p取余数的结果

样例输入

样例输出

样例输入

65536

样例输出

462302286

数据规模和约定

　　对于50%的数据 t<=10^9
　　对于70%的数据 t<=10^15
　　对于100%的数据 t<=10^18

解题思路：看出来是求斐波那契数列第n项了，不过数据范围太大，用O(n)的时间复杂度一定超时。尝试性的提交了一下，看看能不能过几个小数据的样例。

 1 //超时代码 
 2 #include <bits/stdc++.h>
 3 using namespace std; 
 4 const int mod = 1000000007;
 5 typedef long long ll;
 6 int main() {
 7     ll n;
 8     cin >> n;
 9     ll a = 1;
10     ll b = 1;
11     ll ans = 1;
12     for (int i = 2; i <= n; i++) {
13         ans = (a % mod + b % mod) % mod;
14         a = b;
15         b = ans;
16     }
17     cout << ans << endl;
18     return 0;
19 }

结果一个样例没过，下载测试数据发现基本都是10^8级别。

然后学到这道题是矩阵快速幂的模板题目，时间复杂度O(logn)。

先复习一下一般的快速幂。

预备知识：快速幂的百度百科：https://baike.baidu.com/item/%E5%BF%AB%E9%80%9F%E5%B9%82/5500243?fr=aladdin

最一般的快速幂模板：

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int mod = 1000000007;
 5 ll quick_pow(ll x, ll y, ll c) {
 6     ll ans = 1;
 7     while (y) {
 8         if (y & 1) {
 9             ans = (ans * x) % c;
10         }
11         x = (x * x) % c;
12         y >>= 1;
13     }
14     return ans;
15 }
16 int main() {
17     ll x, y, ans;
18     cin >> x >> y;
19     ans = quick_pow(x, y, mod);
20     cout << ans << endl;
21     return 0;
22 }

然后是利用快速乘法优化一下，就是将quick_pow复制一下改名为quick_mul，把ans改为0，所有的乘号改为加号，用于把普通的大数a乘以大数a加速。不过一般用不到，先贴出来备忘，万一哪天用到了。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int mod = 1000000007;
 5 ll quick_mul(ll x, ll y, ll r) {
 6     ll ans = 0;
 7     while (y) {
 8         if (y & 1) {
 9             ans = (ans + x) % r;
10         }
11         x = (x + x) % r;
12         y >>= 1;
13     }
14     return ans;
15 }
16 ll quick_pow(ll x, ll y, ll r) {
17     ll ans = 1;
18     while (y) {
19         if (y & 1) {
20             ans = quick_mul(ans, x, r);
21         }
22         x = quick_mul(x, x, r);;
23         y >>= 1;
24     }
25     return ans;
26 }
27 int main() {
28     ll x, y, ans;
29     cin >> x >> y;
30     ans = quick_pow(x, y, mod);
31     cout << ans << endl;
32     return 0;
33 }

以前没有学过矩阵快速幂的模板，本着学习新知识，分析网上搜来的其他模板整理出一个自己惯用的模板的原则，写出了我很满意的第一版矩阵快速幂模板。

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int mod = 1000000007;
 4 typedef long long ll;
 5 struct Matrix {
 6     ll a[2][2];
 7     Matrix() {
 8         memset(a, 0, sizeof a);
 9     }
10 };
11 Matrix mul(Matrix A, Matrix B) { //返回矩阵A乘矩阵B
12     Matrix C; //C矩阵来存答案 
13     for (int i = 0; i < 2; i++) {
14         for (int k = 0; k < 2; k++) {
15             for (int j = 0; j < 2; j++) {
16                 C.a[i][j] += (A.a[i][k] % mod * B.a[k][j] % mod) % mod;
17             }
18         }
19     }
20     return C; //返回新矩阵 
21 }
22 Matrix pow_mod(Matrix A, int n) { //返回矩阵A的n次方 
23     Matrix B; //存储答案 
24     for (int i = 0; i < 2; i++) { //初始化为单位矩阵 
25         for (int j = 0; j < 2; j++) {
26             B.a[i][j] = (i == j ? 1 : 0);
27         }
28     } 
29     while (n) { //同一般的快速幂 
30         if (n & 1) {
31             B = mul(B, A);
32         }
33         A = mul(A, A);
34         n >>= 1;    
35     }
36     return B;
37 }
38 int main() {
39     int n;
40     cin >> n;
41     Matrix A;
42     A.a[0][0] = A.a[0][1] = A.a[1][0] = 1; //初始化T矩阵 
43     A = pow_mod(A, n - 1);
44     cout << (A.a[0][0] + A.a[0][1]) % mod << endl;
45     return 0;
46 }

结果提交后发现只有50分，查看样例后发现数据量太大时会超时，怀疑是调用c++结构体里的构造函数比较耗时。不过第一版模板的思路逻辑还是挺好的，适合用来复习矩阵快速幂算法。

然后AC的第二版代码，参考自https://blog.csdn.net/cplutoy/article/details/104268207

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int p = 1000000007;
 4 typedef long long ll;
 5 struct Mat {
 6     ll m[2][2];
 7 } ans, base; //ans为答案矩阵， base为需要求次方的矩阵 
 8 Mat Mul(Mat x, Mat y) { //返回矩阵x乘以矩阵y的矩阵 
 9     Mat c;
10     for (int i = 0; i < 2; i++) {
11         for (int j = 0; j < 2; j++) {
12             c.m[i][j] = 0;
13             for (int k = 0; k < 2; k++) {
14                 c.m[i][j] += (x.m[i][k] % p * y.m[k][j] % p) % p;
15             }
16         }
17     }
18     return c;
19 }
20 void quick_pow(ll n) { //求base的n-1次方 
21     while (n) { //同一般的快速幂 
22         if (n & 1) {
23             ans = Mul(ans, base);
24         }
25         base = Mul(base, base);
26         n >>= 1;
27     }
28 }
29 int main() {
30     ll n;
31     cin >> n;
32     ans.m[0][0] = 1, ans.m[0][1] = 0, ans.m[1][0] = 0, ans.m[1][1] = 1; //初始化ans为单位矩阵，
33     base.m[0][0] = 1, base.m[0][1] = 1, base.m[1][0] = 1, base.m[1][1] = 0; //将base初始化为要求n次幂的矩阵
34     quick_pow(n - 1);
35     cout << (ans.m[0][0] + ans.m[0][1]) % p << endl;
36     return 0;
37 }

蓝桥杯 奇异的虫群 矩阵快速幂

蓝桥杯奇异的虫群矩阵快速幂