青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品

為生存而奔跑

   :: 首頁 :: 聯系 :: 聚合  :: 管理
  271 Posts :: 0 Stories :: 58 Comments :: 0 Trackbacks

留言簿(5)

我參與的團隊

搜索

  •  

積分與排名

  • 積分 - 331734
  • 排名 - 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 閱讀(266) 評論(0)  編輯 收藏 引用 所屬分類: Algorithm
青青草原综合久久大伊人导航_色综合久久天天综合_日日噜噜夜夜狠狠久久丁香五月_热久久这里只有精品
  • <ins id="pjuwb"></ins>
    <blockquote id="pjuwb"><pre id="pjuwb"></pre></blockquote>
    <noscript id="pjuwb"></noscript>
          <sup id="pjuwb"><pre id="pjuwb"></pre></sup>
            <dd id="pjuwb"></dd>
            <abbr id="pjuwb"></abbr>
            亚洲国产高清一区| 好吊日精品视频| 亚洲伊人伊色伊影伊综合网 | 国产精品成人免费视频| 欧美国产一区视频在线观看 | 亚洲伦理在线| 亚洲深夜影院| 欧美综合国产精品久久丁香| 久久精品国产在热久久| 玖玖综合伊人| 欧美日韩色综合| 国产欧美一区二区精品婷婷 | 国产精品亚洲综合色区韩国| 国产一区二区看久久| 亚洲精品久久久久久下一站| 亚洲图片自拍偷拍| 久久久久久亚洲精品杨幂换脸 | 午夜在线观看免费一区| 久久久精品视频成人| 欧美日韩第一页| 国产一区二区激情| 亚洲美女视频| 久久久久国产精品人| 亚洲日本乱码在线观看| 国产精品99久久久久久www| 亚洲一级在线| 欧美风情在线| 午夜久久久久| 欧美日韩午夜在线视频| 狠狠色狠狠色综合人人| 亚洲午夜精品久久| 欧美成人69av| 久久av免费一区| 国产精品自在在线| 亚洲小说欧美另类婷婷| 亚洲国产成人在线视频| 久久精品视频99| 国产欧美日韩另类一区| 正在播放亚洲一区| 免费看亚洲片| 久久精品视频在线看| 国产农村妇女毛片精品久久麻豆 | 91久久精品美女高潮| 欧美综合激情网| 国产欧美日韩精品丝袜高跟鞋| 亚洲开发第一视频在线播放| 久久综合伊人77777| 亚洲专区一区二区三区| 欧美日韩一区二区精品| 亚洲精品在线观| 欧美高清视频在线播放| 久久久www| 黄色欧美成人| 老司机aⅴ在线精品导航| 亚洲欧美在线aaa| 国产精品男女猛烈高潮激情| 亚洲婷婷综合久久一本伊一区| 欧美激情va永久在线播放| 久久精品久久综合| 狠狠色丁香久久婷婷综合丁香| 欧美一区二区三区视频在线观看| 夜夜嗨av一区二区三区网页| 欧美日韩高清在线| 在线亚洲欧美专区二区| 99精品国产一区二区青青牛奶 | 国产精品久久久久秋霞鲁丝| 亚洲图色在线| 亚洲在线观看免费| 国产一区二区久久精品| 蜜臀a∨国产成人精品| 久久久久久网址| 亚洲精品视频在线播放| 亚洲精品免费一区二区三区| 欧美日韩国产综合视频在线| 亚洲一区高清| 欧美在线免费视频| 亚洲七七久久综合桃花剧情介绍| 亚洲国产精选| 亚洲制服丝袜在线| 国产一级久久| 欧美肥婆bbw| 欧美色精品在线视频| 午夜精品久久久久久99热| 亚洲欧美中文日韩v在线观看| 国产亚洲网站| 欧美国产日韩一区二区| 欧美视频一区二区三区…| 欧美一区二区三区喷汁尤物| 久久嫩草精品久久久精品| 99国产精品自拍| 亚洲在线国产日韩欧美| 一区二区三区在线不卡| 亚洲毛片在线观看| 黑人一区二区三区四区五区| 亚洲国产成人久久| 国产精品手机在线| 久久综合给合久久狠狠色| 欧美日本韩国| 久久久免费观看视频| 欧美日韩亚洲一区二区三区在线观看 | 一区二区三区导航| 狠狠色噜噜狠狠色综合久| 亚洲日本aⅴ片在线观看香蕉| 国产欧美激情| 亚洲日本在线观看| 激情综合色丁香一区二区| 一本久道久久综合婷婷鲸鱼| 精品av久久久久电影| 亚洲一区二区精品在线观看| 亚洲精品视频免费在线观看| 欧美在线观看视频在线| 亚洲视频电影图片偷拍一区| 久久久亚洲欧洲日产国码αv| 亚洲男女自偷自拍| 欧美日韩第一页| 亚洲成色777777女色窝| 国内外成人在线| 亚洲欧美视频一区| 亚洲一区二区在线免费观看| 久久在线91| 久久综合导航| 禁久久精品乱码| 久久国产免费看| 欧美伊人影院| 国产麻豆9l精品三级站| 中日韩在线视频| 亚洲影视九九影院在线观看| 欧美激情视频给我| 亚洲黄色成人久久久| 亚洲激情另类| 蜜桃av一区二区三区| 欧美成人精品福利| 在线欧美不卡| 噜噜噜躁狠狠躁狠狠精品视频| 久久久另类综合| 在线观看成人网| 另类欧美日韩国产在线| 欧美777四色影视在线| 伊人色综合久久天天| 久久久久久久成人| 日韩亚洲不卡在线| 牛人盗摄一区二区三区视频| 欧美a级大片| 亚洲欧洲免费视频| 欧美人与性动交cc0o| 亚洲美女黄网| 欧美一区二区三区的| 国内精品久久久久影院薰衣草| 久久久水蜜桃av免费网站| 亚洲第一福利社区| aaa亚洲精品一二三区| 国产精品vvv| 亚洲专区一区| 免费国产自线拍一欧美视频| 亚洲激情网址| 欧美午夜www高清视频| 先锋a资源在线看亚洲| 裸体一区二区| 一个色综合av| 国产亚洲网站| 欧美激情视频在线免费观看 欧美视频免费一 | 国产日本欧美一区二区三区| 久久成年人视频| 亚洲国产精品一区二区第四页av| 一个色综合导航| 韩国av一区二区| 欧美日韩国产一级片| 欧美一级视频一区二区| 欧美激情一区二区三区高清视频| 日韩午夜在线电影| 国产一区二区三区久久悠悠色av| 麻豆久久精品| 亚洲欧美日韩精品| 亚洲黄色天堂| 久久久九九九九| 在线视频一区观看| 激情综合色综合久久综合| 欧美美女福利视频| 欧美在线不卡| 亚洲视屏一区| 亚洲人成人99网站| 久久蜜桃精品| 午夜激情久久久| 亚洲理论在线观看| 国产亚洲精品激情久久| 欧美日韩国产va另类| 久久影视精品| 欧美专区18| 香蕉av777xxx色综合一区| 亚洲经典三级| 久久深夜福利| 久久成人在线| 亚洲免费在线播放| 亚洲乱码国产乱码精品精| 国产一区二区三区在线观看精品| 欧美日韩午夜在线视频| 欧美精品二区三区四区免费看视频| 久久久999国产| 久久久成人网| 久久精品视频在线免费观看|