首页 > 代码库 > uva10229-模Fibonacci
uva10229-模Fibonacci
题目链接 http://vjudge.net/problem/UVA-10229
解题思路
一开始想到一种O（n）的算法，就是每次只算fib的二进制后m位，然后就TLE了。。。
比较正确的解法是用矩阵快速幂。大概是O（log（n））的算法，对任何数据都很快。。。
要注意n=0的情况。。。
代码
#include<stdio.h>#include<string.h>typedef long long ll;ll ans[2][1], t[2][2] = {1}, s[2][2];ll base[2][2] = {0, 1, 1, 1};ll mod;void copy(ll a[][2], ll b[][2]){ for(int i=0; i<2; i++) for(int j=0; j<2; j++) a[i][j] = b[i][j];}void mul(ll a[][2], ll b[][2], ll c[][2]){ for(int i=0; i<2; i++) for(int j=0; j<2; j++) a[i][j] = 0; for(int i=0; i<2; i++) for(int j=0; j<2; j++) for(int k=0; k<2; k++) a[i][j] += (b[i][k] * c[k][j]) % mod;}int cal(ll n){ if(n == 1) copy(s, base); else { cal(n/2); copy(t, s); mul(s, t, t); if(n % 2 == 1){ mul(t, s, base); copy(s, t); } }}int main(){ int n, m; while(scanf("%d%d", &n, &m) == 2) { if(n >= 1) { mod = 1 << m; cal(n); printf("%d\n", s[0][1]%mod); } else printf("0\n"); } return 0;}
uva10229-模Fibonacci
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。