The Fourth Dimension Space

枯叶北风寒，忽然年以残，念往昔，语默心酸。二十光阴无一物，韶光贱，寐难安； 不畏形影单，道途阻且慢，哪曲折，如渡飞湍。斩浪劈波酬壮志，同把酒，共言欢！ -如梦令

ZOJ 2105 矩阵乘法(求线性常系数差分方程第N项)

DIY群上说可以用暴力循环节的方法来做，的确也是不错的，不过练题的本质在于学到新的东西，所以就用矩阵乘法敲了，恩 感觉收获还是蛮大的，掌握了和矩阵相关的很多运算。
#include<iostream>
#include<algorithm>
using namespace std;

struct matrix
{
    int n,m;
    int a[2][2];
    matrix operator *(matrix other)
    {
        int i,j;
        matrix res;
        res.n=n;
        res.m=other.m;
        for(i=0;i<n;i++)
            for(j=0;j<m;j++)
            {
                res.a[i][j]=0;
                for(int k=0;k<m;k++)
                {
                    res.a[i][j]+=a[i][k]*other.a[k][j];
                    if(res.a[i][j]>=7)
                        res.a[i][j]%=7;
                }
            }
        return res;
    }

    matrix operator +(matrix other)
    {
        matrix res;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
            {

                res.a[i][j]=a[i][j]+other.a[i][j];
                if(res.a[i][j]>=7)
                    res.a[i][j]%=7;
            }
        return res;

    }
};

matrix a;
matrix ans;
int A,B,n;
matrix g(int k)//算A^k
{
    matrix t;
    if(k==1)
        return a;
    if(k&1)
    {
        t=g(k>>1);
        t=t*t;
        t=t*a;
    }
    else
    {
        t=g(k>>1);
        t=t*t;
    }
    return t;
}

void init()
{
    a.n=2;a.m=2;
    a.a[0][0]=0;
    a.a[0][1]=1;
    a.a[1][0]=B;
    a.a[1][1]=A;
    //////////////////////////////////////////////////////////////////////////
    ans.n=2;
    ans.m=1;
    ans.a[0][0]=1;
    ans.a[1][0]=1;
}


int main()
{
    int i,j;
    
    

    while(scanf("%d%d%d",&A,&B,&n)!=EOF)
    {

        if(A==0&&B==0&&n==0)
            break;
        if(n==1||n==2)
        {
            printf("1\n");
            continue;
        }
        init();
        a=g(n-2);
        ans=a*ans;
        printf("%d\n",ans.a[1][0]);
    }
    return 0;
}

posted on 2010-05-21 22:31 abilitytao 阅读(1416) 评论(0)  编辑 收藏 引用


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