UVA10518 How Many Calls? —— 矩阵快速幂

题目链接：https://vjudge.net/problem/UVA-10518

题解：

问：求斐波那契数f[n]的时候调用了多少次f[n] = f[n-1] + f[n-2]，没有记忆化，一直递归到f[0]、f[1]，其中f[0]、f[1]也算调用了一次。

设求f[n]调用了S[n]次，则可知： S[n] = S[n-1] + S[n-2] + 1。构造矩阵求解即可。

代码如下：

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <algorithm>
 5 #include <vector>
 6 #include <cmath>
 7 #include <queue>
 8 #include <stack>
 9 #include <map>
10 #include <string>
11 #include <set>
12 using namespace std;
13 typedef long long LL;
14 const int INF = 2e9;
15 const LL LNF = 9e18;
16 //const int MOD = 1e9+7;
17 const int MAXN = 1e6+100;
18 
19 int MOD;
20 const int Size = 3;
21 struct MA
22 {
23     LL mat[Size][Size];
24     void init()
25     {
26         for(int i = 0; i<Size; i++)
27         for(int j = 0; j<Size; j++)
28             mat[i][j] = (i==j);
29     }
30 };
31 
32 MA mul(MA x, MA y)
33 {
34     MA ret;
35     memset(ret.mat, 0, sizeof(ret.mat));
36     for(int i = 0; i<Size; i++)
37     for(int j = 0; j<Size; j++)
38     for(int k = 0; k<Size; k++)
39         ret.mat[i][j] += 1LL*x.mat[i][k]*y.mat[k][j]%MOD, ret.mat[i][j] %= MOD;;
40     return ret;
41 }
42 
43 MA qpow(MA x, LL y)
44 {
45     MA s;
46     s.init();
47     while(y)
48     {
49         if(y&1) s = mul(s, x);
50         x = mul(x, x);
51         y >>= 1;
52     }
53     return s;
54 }
55 
56 MA tmp ={
57     1, 1, 1,
58     1, 0, 0,
59     0, 0, 1
60 };
61 
62 int main()
63 {
64     LL n, b, f[2] = {1,1}, kase = 0;
65     while(scanf("%lld%lld",&n,&b)&&(n||b))
66     {
67         MOD = b;
68         if(n<=1)
69         {
70             printf("Case %lld: %lld %lld %lld
", ++kase, n, b, f[n]%MOD);
71             continue;
72         }
73 
74         MA s = tmp;
75         s = qpow(s, n-1);
76         LL ans = ((s.mat[0][0]+s.mat[0][1])%MOD+s.mat[0][2])%MOD;
77         printf("Case %lld: %lld %lld %lld
", ++kase, n, b, ans);
78     }
79 }

View Code