首页 > 其他 > 详细

POJ 3070 Fibonacci.(矩阵快速幂)

时间:2015-03-24 23:05:47      阅读:370      评论:0      收藏:0      [点我收藏+]

解题思路:用公式递推显然是会超时的,于是根据题目明显的提示,就想到用矩阵快速幂。

之所以快,是运用了二分的思想,算出了矩阵A的值,那么我可以一步算出A*A的值,进而一步算出A*A*A*A的值,进而……

题目链接:点击打开链接

#include<cstdio>
#include<algorithm>
#define N 100000
#define MOD 10000
using namespace std;

int f[N];
int Get(int n) //将n转化成二进制并存到数组f
{
    int cnt=0;
    while(n)
    {
        if(n%2) f[cnt++]=1;
        else f[cnt++]=0;
        n/=2;
    }
    return cnt;
}
int b[2][2],s[2][2]; //数组b保存矩阵A,A*A,A*A*A*A……数组s保存答案。
void Cal(int k)
{
    int t[2][2];
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            t[i][j]=s[i][j];
    if(k) //此二进制位为1.
    {
        s[0][0]=((t[0][0]*b[0][0])%MOD+(t[0][1]*b[1][0])%MOD)%MOD; //矩阵乘法
        s[0][1]=((t[0][0]*b[0][1])%MOD+(t[0][1]*b[1][1])%MOD)%MOD;
        s[1][0]=((t[1][0]*b[0][0])%MOD+(t[1][1]*b[1][0])%MOD)%MOD;
        s[1][1]=((t[1][0]*b[0][1])%MOD+(t[1][1]*b[1][1])%MOD)%MOD;
    }
    for(int i=0;i<2;i++)
        for(int j=0;j<2;j++)
            t[i][j]=b[i][j];
    //继续求下一个A*A*A*A*A*A*A*A……
    b[0][0]=((t[0][0]*t[0][0])%MOD+(t[0][1]*t[1][0])%MOD)%MOD; 
    b[0][1]=((t[0][0]*t[0][1])%MOD+(t[0][1]*t[1][1])%MOD)%MOD;
    b[1][0]=((t[1][0]*t[0][0])%MOD+(t[1][1]*t[1][0])%MOD)%MOD;
    b[1][1]=((t[1][0]*t[0][1])%MOD+(t[1][1]*t[1][1])%MOD)%MOD;
}
int main()
{
    int n;
    while(scanf("%d",&n)==1)
    {
        if(n==-1)
            break;
        int len=Get(n);
        b[0][0]=1; b[0][1]=1; b[1][0]=1; b[1][1]=0;  //初始化。
        s[0][0]=1; s[0][1]=0; s[1][0]=0; s[1][1]=1;
        for(int i=0;i<len;i++)
            Cal(f[i]);
        printf("%d\n",s[0][1]);
    }
    return 0;
}



POJ 3070 Fibonacci.(矩阵快速幂)

原文:http://blog.csdn.net/darwin_/article/details/44598983

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!