为生存而奔跑
   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

随笔分类

随笔档案

相册

搜索

  •  

积分与排名

  • 积分 - 323490
  • 排名 - 74

最新评论

阅读排行榜

评论排行榜
【矩阵问题】PKU 3070
pku 3070
题目要求计算Fibonacci数列的第n项最后4位。因为n可以很大(0 ≤ n ≤ 1,000,000,000)。因此直接计算在时限内是不可能的（有多个case）。题目还给出了计算的方法：表示成矩阵连乘的形式为



求第n项的后4位，相当于求第n项模10000的余数。而矩阵的乘法满足边乘边模。矩阵乘法还满足结合律，所以可以先计算出上面的一个矩阵的2的幂次方的值，记录下来。然后对于每一个n，将它表示成2进制。如当n=5时，只需计算一次矩阵乘法：1次方乘以4次方。当n=1000000000时最多只需计算29次矩阵乘法2^29 = 536870912）
#include<iostream>
#include<algorithm>
#include<string>
#include<vector>
#include<cmath>
#include<map>
using namespace std;
int m[31][4],fact[31];
int n;
void init()
{
    fact[1]=1;
    m[1][0]=1;    m[1][1]=1;    m[1][2]=1;    m[1][3]=0;
    for(int i=2;i<=30;i++)
    {
        m[i][0]=(m[i-1][0]*m[i-1][0]+m[i-1][1]*m[i-1][2])%10000;
        m[i][1]=(m[i-1][0]*m[i-1][1]+m[i-1][1]*m[i-1][3])%10000;
        m[i][2]=(m[i-1][2]*m[i-1][0]+m[i-1][3]*m[i-1][2])%10000;
        m[i][3]=(m[i-1][2]*m[i-1][1]+m[i-1][3]*m[i-1][3])%10000;
        fact[i]=fact[i-1]*2;
    }
}
void solve()
{
    bool vis[31]={0};  // 对n表示成2进制
    for(int i=30;i>0;i--)
        if(n>=fact[i])
        {
            n-=fact[i];
            vis[i]=1;
        }
    int res[4]={1,0,0,1};  //单位矩阵
    int tmp[4];
     for(int i=1;i<=30;i++)
    {
        if(vis[i])
        {
            tmp[0]=(res[0]*m[i][0]+res[1]*m[i][2])%10000;
            tmp[1]=(res[0]*m[i][1]+res[1]*m[i][3])%10000;
            tmp[2]=(res[2]*m[i][0]+res[3]*m[i][2])%10000;
            tmp[3]=(res[2]*m[i][1]+res[3]*m[i][3])%10000;
            for(int j=0;j<4;j++)
                res[j]=tmp[j];
        }
    }
    printf("%d\n",res[1]);
}
int main()
{
    init();
    while(scanf("%d",&n)!=EOF&&n!=-1)
    {
        solve();
    }
}
posted on 2009-08-17 10:57 baby-fly 阅读(253) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理