poj 3070 Fibonacci 矩阵快速幂

谁借莪１个温暖的怀抱￠ 2022-08-08 05:21 152阅读 0赞

#include <cstdio>
    #include <cstring>
    using namespace std;
    
    #define M_H 2
    #define M_L 2
    
    typedef struct ma
    {
        int h, l;
        int a[M_H][M_L];
    }ma;
    ma need, anser;
    void init()
    {
        need.h=2;   need.l=2;
        anser.h=2;  anser.l=2;
        need.a[0][0]=1; anser.a[0][0]=1;
        need.a[0][1]=1; anser.a[0][1]=0;
        need.a[1][0]=1; anser.a[1][0]=0;
        need.a[1][1]=0; anser.a[1][1]=1;
    }
    
    ma multi(ma a, ma b)
    {
        ma c;
    
        c.h=a.h;  c.l=b.l;
        for(int i=0; i<c.h; i++) for(int j=0; j<c.l; j++) c.a[i][j]=0;
    
        for(int i=0; i<c.h; i++){
            for(int j=0; j<c.l; j++){
                int ans=0;
                for(int k=0; k<a.h; k++){
                    ans += (a.a[i][k] * b.a[k][j])%10000;
                }
                c.a[i][j]=ans%10000;
            }
        }
        return c;
    }
    int main()
    {
        int m;
    
        while( scanf("%d", &m) != -1 ){
            if(m==-1) break;
            init();
            while(m>0){
                if(m&1){
                    anser = multi(anser, need);
                }
                need = multi(need, need);
                m = m>>1;
            }
            printf("%d\n", anser.a[0][1]%10000);
        }
    
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，152人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj3233(矩阵快速幂)

Matrix Power Series <table> <tbody> <tr> <td><strong>Time Limit:</strong>&nbsp

雨点打透心脏的1/2处/ 2024年02月17日 19:21/ 0 赞/ 12 阅读

相关 poj3070 矩阵快速幂

Fibonacci <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</t

古城微笑少年丶/ 2024年02月17日 19:21/ 0 赞/ 21 阅读

相关 poj 3070 Fibonacci 矩阵快速幂

include <cstdio> include <cstring> using namespace std; define M_H

谁借莪１个温暖的怀抱￠/ 2022年08月08日 05:21/ 0 赞/ 153 阅读

相关 poj 3070 矩阵快速幂

poj3070 include <cstdio> include <cstring> using namespace std;

￡神魔★判官ぃ/ 2022年08月07日 14:53/ 0 赞/ 121 阅读

相关 poj-3734(矩阵快速幂+推导)

问题描述: Panda has received an assignment of painting a line of blocks. Since Panda is suc

妖狐艹你老母/ 2022年06月09日 04:26/ 0 赞/ 186 阅读

相关 poj3744（概率dp+矩阵快速幂）

<table style="background-image:url("http://poj.org/images/table_back.jpg");fon

女爷i/ 2022年05月30日 12:28/ 0 赞/ 195 阅读

相关 poj Fibonacci 矩阵快速幂

题目链接：[点我][Link 1] Description In the Fibonacci integer sequence, F0 = 0, F1 = 1, and

向右看齐/ 2022年05月16日 11:22/ 0 赞/ 164 阅读

相关 uva 10229 - Modular Fibonacci(矩阵快速幂）

[题目链接：uva 10229 - Modular Fibonacci][uva 10229 - Modular Fibonacci] 题目大意：给出n和m，求出f

梦里梦外;/ 2022年05月12日 23:16/ 0 赞/ 135 阅读

相关 POJ 3070 Fibonacci——————矩阵快速幂解法

\\Fibonacci \\ Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 19481 Acce

浅浅的花香味﹌/ 2022年05月10日 11:34/ 0 赞/ 149 阅读

相关 POJ3070Fibonacci（矩阵快速幂）

在斐波那契数列中，Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1) 。给定整数n，求Fibnmod10000 。输入格式输入包含多组

小咪咪/ 2021年10月25日 12:22/ 0 赞/ 301 阅读