矩阵快速幂，求模板。。。 - C语言论坛

已结贴√ 问题点数：20 回复次数：4

矩阵快速幂，求模板。。。

最近学快速幂，一个人乱打乱撞。求调教~
http://218.194.91.48/acmhome/problemdetail.do?&method=showdetail&id=1302
题目如上。

貌似是这样的：        1 1 1                         1                f(n)
                (     1 0 0      ) ^( n-3） * (     1     ) =  (     f(n-1)    )
                      0 1 0                         1                f(n-2)

大括号不会打，囧。
知道是要用矩阵快速幂，从网上搜了一些资料。第一次做这个，写了一段代码，好搓。
本人认真思考过，不是求作业。。。。。。只为提高。。。。。
这个到底是哪错了呢？求模板啊。

程序代码：

#include<iostream>
#include<cstdio>
using namespace std;
struct Matrix{
    __int64 map[3][3];
};
Matrix operator*(Matrix a,Matrix b)
{
    int i,j,k;
    Matrix tmp;
    for(i=0;i<3;++i)
        for(j=0;j<3;++j){
            __int64 all=0;
            for(k=0;k<3;++k){
                all+=(a.map[i][k]%10000007)*(b.map[k][j]%10000007)%10000007;
                all%=10000007;
            }
            tmp.map[i][j]=all;
        }
    return tmp;
}

__int64 MatrixT(int p)
{
    Matrix f,e,rt;
    int i,j;
    for(i=0;i<3;++i){
        f.map[i][0]=1;
        for(j=0;j<3;++j){
            e.map[i][j]=0;
            if(i==0||(i==1&&j==0)||(i==2&&j==1))
                e.map[i][j]=1;
            if(i==j)    rt.map[i][j]=1;
        }
    }
    if(p==1)    rt=e*f;
    else{
        while(p){
            if(p&1)    rt=rt*e;
             e=e*e;
            p>>=1;    
        }
        rt=rt*f;
    }
    return rt.map[0][0]%10000007;
} 
int main()
{
    int n;
    while(~scanf("%d",&n)){
        if(n==1||n==2||n==3)    printf("1\n");
        else printf("%I64d\n",MatrixT(n-3));
    }
    return 0;
}

[ 本帖最后由 cb_1212 于 2012-3-22 12:26 编辑 ]

搜索更多相关主题的帖子: 资料　大括号　 method　快速　

#include<iostream> #include<cstdio> using namespace std; struct Matrix{ __int64 map[3][3]; }; Matrix operator*(Matrix a,Matrix b) { int i,j,k; Matrix tmp; for(i=0;i<3;++i) for(j=0;j<3;++j){ tmp.map[i][j]=0; for(k=0;k<3;++k) tmp.map[i][j]+=(a.map[i][k]%10000007)*(b.map[k][j]%10000007)%10000007; tmp.map[i][j]%=10000007; } return tmp; } __int64 MatrixT(int p) { Matrix f,a,rt; int i,j; for(i=0;i<3;++i){ f.map[i][0]=1; for(j=0;j<3;++j){ a.map[i][j]=0; if(i==0||(i==1&&j==0)||(i==2&&j==1)) a.map[i][j]=1; rt.map[i][j]=0; if(i==j) rt.map[i][j]=1; } } if(p==1) rt=a*f; else{ while(p){ if(p&1) rt=rt*a; p>>=1; a=a*a; } rt=rt*f; } return rt.map[0][0]%10000007; } int main() { int n; while(~scanf("%d",&n)){ if(n==1||n==2||n==3) printf("1\n"); else printf("%I64d\n",MatrixT(n-3)); } return 0; }