POJ-3070Fibonacci（矩阵快速幂求Fibonacci数列） uva 10689 Yet another Number Sequence【矩阵快速幂】

典型的两道矩阵快速幂求斐波那契数列

POJ 那是默认a=0，b=1

UVA 一般情况是斐波那契f（n）=(n-1)次幂情况下的（ans.m[0][0] * b + ans.m[0][1] * a）；

 1 //POJ
 2 #include <cstdio>
 3 #include <iostream>
 4 
 5 using namespace std;
 6 
 7 const int MOD = 10000;
 8 
 9 struct matrix
10 {
11     int m[2][2];
12 }ans, base;
13 
14 matrix multi(matrix a, matrix b)
15 {
16     matrix tmp;
17     for(int i = 0; i < 2; ++i)
18     {
19         for(int j = 0; j < 2; ++j)
20         {
21             tmp.m[i][j] = 0;
22             for(int k = 0; k < 2; ++k)
23                 tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
24         }
25     }
26     return tmp;
27 }
28 int fast_mod(int n)  // 求矩阵 base 的  n 次幂 
29 {
30     base.m[0][0] = base.m[0][1] = base.m[1][0] = 1;
31     base.m[1][1] = 0;
32     ans.m[0][0] = ans.m[1][1] = 1;  // ans 初始化为单位矩阵 
33     ans.m[0][1] = ans.m[1][0] = 0;
34     while(n)
35     {
36         if(n & 1)  //实现 ans *= t; 其中要先把 ans赋值给 tmp，然后用 ans = tmp * t 
37         {
38             ans = multi(ans, base);
39         }
40         base = multi(base, base);
41         n >>= 1;
42     }
43     return ans.m[0][1];
44 }
45 
46 int main()
47 {
48     int n;
49     while(scanf("%d", &n) && n != -1)
50     {   
51         printf("%d
", fast_mod(n));
52     }
53     return 0;
54 }

View Code

 1 //uva
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<iostream>
 6 #include<cstdlib>
 7 #include<string>
 8 #include<cmath>
 9 #include<vector>
10 using namespace std;
11 const int maxn=1e5+7;
12 const double eps=1e-8;
13 const double pi=acos(-1);
14 #define ll long long
15 const int MOD = 10000;
16 
17 int a,b,n,m;
18 struct matrix
19 {
20     int m[2][2];
21 } ans, base;
22 
23 matrix multi(matrix a, matrix b)
24 {
25     matrix tmp;
26     for(int i = 0; i < 2; ++i)
27     {
28         for(int j = 0; j < 2; ++j)
29         {
30             tmp.m[i][j] = 0;
31             for(int k = 0; k < 2; ++k)
32                 tmp.m[i][j] = (tmp.m[i][j] + a.m[i][k] * b.m[k][j]) % MOD;
33         }
34     }
35     return tmp;
36 }
37 int fast_mod(int n)  // 求矩阵 base 的  n 次幂
38 {
39     base.m[0][0] = base.m[0][1] = base.m[1][0] = 1;
40     base.m[1][1] = 0;
41     ans.m[0][0] = ans.m[1][1] = 1;  // ans 初始化为单位矩阵
42     ans.m[0][1] = ans.m[1][0] = 0;
43     while(n)
44     {
45         if(n & 1)  //实现 ans *= t; 其中要先把 ans赋值给 tmp，然后用 ans = tmp * t
46         {
47             ans = multi(ans, base);
48         }
49         base = multi(base, base);
50         n >>= 1;
51     }
52 //    return ans.m[0][1];
53 }
54 
55 int main()
56 {
57     int t;
58     scanf("%d",&t);
59     while (t--)
60     {
61         scanf("%d%d%d%d",&a,&b,&n,&m);
62         m = pow(10, m);
63         if (n == 0)
64         {
65             printf("%d
", (a%m + m) % m);
66             continue;
67         }
68         if (n == 1)
69         {
70             printf("%d
", (b%m + m) % m);
71             continue;
72         }
73         fast_mod(n-1);
74         int tmp = ((ans.m[0][0] * b + ans.m[0][1] * a) % m + m) % m;
75         printf("%d
", tmp);
76     }
77     return 0;
78 }

View Code