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

cb_1212

等　级：新手上路
帖　子：126
专家分：5
注　册：2011-4-28
结帖率：66.67%

楼主

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

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

最近学快速幂，一个人乱打乱撞。求调教~
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　快速　

2012-03-22 00:36

cb_1212

等　级：新手上路
帖　子：126
专家分：5
注　册：2011-4-28

第 3 楼

得分:0

改了一下，一次AC。第一次做矩阵，水题秒过也挺开心的，哈哈。

程序代码：

#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;
}

2012-03-22 13:12