UVA 10518 How Many Calls?

本文主要是介绍UVA 10518 How Many Calls?，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题意：涉及到矩阵的快速幂取模，这里有一篇关于快速幂取模的文章点击打开链接，题目要求的是求函数F(n)计算的次数，然后输出f(n) MOD m的结果，很容易知道f(n)=f(n-1)+f(n-2)+1,

然后又看了这篇分析

点击打开链接

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;struct node{int s[2][2];
}a,p,ans;
int m;void init(){a.s[0][0]=1,ans.s[0][0]=1;a.s[0][1]=1,ans.s[0][1]=0;a.s[1][0]=1,ans.s[1][0]=0;a.s[1][1]=0,ans.s[1][1]=1;
}node calcu(node a,node b){for (int i = 0; i < 2; i++)for (int j = 0; j < 2; j++)p.s[i][j] = (a.s[i][0]*b.s[0][j]+a.s[i][1]*b.s[1][j])%m;return p;    
}int solve(long long s){init();while (s){if (s & 1)ans = calcu(ans,a);a = calcu(a,a);s >>= 1;}return (ans.s[0][0]*2-1+m)%m;
}int main(){long long n;int cas = 1;while (scanf("%lld%d",&n,&m) != EOF && n+m){printf("Case %d: %lld %d ",cas++,n,m);printf("%d\n",solve(n));}
}

这篇关于UVA 10518 How Many Calls?的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---