为生存而奔跑

   :: 首页 :: 联系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 324333
  • 排名 - 74

最新评论

阅读排行榜

评论排行榜

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 阅读(254) 评论(0)  编辑 收藏 引用 所属分类: Algorithm

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