首页 > 代码库 > UVA10518 - How Many Calls?(矩阵快速幂)
UVA10518 - How Many Calls?(矩阵快速幂)
UVA10518 - How Many Calls?(矩阵快速幂)
题目链接
题目大意:给你fibonacci数列怎么求的,然后问你求f(n) = f(n - 1) + f(n - 2)需要多少次调用,并且这个数很大,取模一个进制的数。
解题思路:要发现F(n) = 2 *f(n) - 1这个规律,估计要很熟系fibonacci数列,我明明推出了好多项后但是一点也没有发现规律。然后要用矩阵快速幂来求fibonacci,因为n很大。构造这样的矩阵
1, 1 (2*2矩阵) * f(n - 1) (2*1矩阵) 等于 f(n - 1) + f(n - 2)(2*1矩阵)
1, 0 f (n - 2) f(n - 1)
这样就可以用前面的那么系数矩阵的n次幂乘上f(1) 这个矩阵得到最后想要的答案。
f(0)
代码:
#include <cstdio>
#include <cstring>
typedef long long ll;
const int maxn = 2;
int base;
struct Mat {
int s[maxn][maxn];
void init () {
s[0][0] = s[0][1] = s[1][0] = 1;
s[1][1] = 0;
}
Mat operator ^ (const Mat& t) const {
Mat arr;
memset (arr.s, 0, sizeof(arr.s));
for (int i = 0; i < maxn; i++)
for (int j = 0; j < maxn; j++)
for (int k = 0; k < maxn; k++)
arr.s[i][j] = (arr.s[i][j] + s[i][k] * t.s[k][j]) % base;
return arr;
}
};
Mat Fmod (ll n, Mat a) {
if (n == 1)
return a;
Mat tmp = Fmod(n/2, a);
tmp = tmp ^ tmp;
if (n % 2 == 1)
tmp = tmp ^ a;
/* printf ("%lld\n", n);
for (int i = 0; i < maxn; i++)
printf ("%d %d\n", tmp.s[i][0], tmp.s[i][1]);*/
return tmp;
}
int main () {
ll n;
int cas = 0;
Mat a, ans;
while (scanf ("%lld%d", &n, &base) && (n || base)) {
a.init();
if (n)
ans = Fmod(n, a);
else
ans = a;
printf ("Case %d: %lld %d %d\n", ++cas, n, base, (ans.s[0][0] * 2 + base - 1) % base);
}
return 0;
}
UVA10518 - How Many Calls?(矩阵快速幂)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。