题目链接: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。构造矩阵求解即可。
代码如下:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
//const int MOD = 1e9+7;
const int MAXN = 1e6+; int MOD;
const int Size = ;
struct MA
{
LL mat[Size][Size];
void init()
{
for(int i = ; i<Size; i++)
for(int j = ; j<Size; j++)
mat[i][j] = (i==j);
}
}; MA mul(MA x, MA y)
{
MA ret;
memset(ret.mat, , sizeof(ret.mat));
for(int i = ; i<Size; i++)
for(int j = ; j<Size; j++)
for(int k = ; k<Size; k++)
ret.mat[i][j] += 1LL*x.mat[i][k]*y.mat[k][j]%MOD, ret.mat[i][j] %= MOD;;
return ret;
} MA qpow(MA x, LL y)
{
MA s;
s.init();
while(y)
{
if(y&) s = mul(s, x);
x = mul(x, x);
y >>= ;
}
return s;
} MA tmp ={
, , ,
, , ,
, ,
}; int main()
{
LL n, b, f[] = {,}, kase = ;
while(scanf("%lld%lld",&n,&b)&&(n||b))
{
MOD = b;
if(n<=)
{
printf("Case %lld: %lld %lld %lld\n", ++kase, n, b, f[n]%MOD);
continue;
} MA s = tmp;
s = qpow(s, n-);
LL ans = ((s.mat[][]+s.mat[][])%MOD+s.mat[][])%MOD;
printf("Case %lld: %lld %lld %lld\n", ++kase, n, b, ans);
}
}