HDU 1005 Number Sequence

题目在这里>_<

题意

给出一个数列定义如下：
$f(1)=1,f(2)=1,f(n)=Af(n-1)+Bf(n-2)$
给你$A,B,n$，计算$f(n)$.

思路

矩阵快速幂裸题。按照$A,B$构造矩阵即可。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <vector>
#include <queue>
#include <iostream>
#include <map>
#include <set>
//#define test
using namespace std;
const int Nmax=7;
typedef long long ll;
const int mod=7;
struct Matrix
{
    int n,m;
    int map[Nmax][Nmax];
    Matrix(int x,int y)
    {
        n=x;m=y;
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                map[i][j]=0;
    }
    Matrix operator * (const Matrix b)
    {
        Matrix c(n,b.m);
        if(m==b.n)
        {
            for(int i=1;i<=c.n;i++)
                for(int k=1;k<=m;k++)
                    for(int j=1;j<=c.m;j++)
                        c.map[i][j]=(c.map[i][j]+(map[i][k]*b.map[k][j])%mod)%mod;
            return c;
        }
        printf("error!!!!!!!!!!!!!!\n");   
        return c;
    }
    Matrix operator + (const Matrix b)
    {
        Matrix c(n,m);
        if(m==b.m && n==b.n)
        {
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    c.map[i][j]=(map[i][j]+b.map[i][j])%mod;
            return c;
        }
        printf("error!!!!!!!!!!!!!!\n");   
        return c;
    }
    void show()
    {
        printf("n:%d m:%d\n",n,m);
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)
                printf("%4d%c",map[i][j],j==m?'\n':' ');
    }
};
int a,b,n;
int work()
{
    Matrix base(2,2);
    base.map[1][1]=a,base.map[1][2]=b;
    base.map[2][1]=1;
    //base.show();
    Matrix ans(2,2);
    ans.map[1][1]=1,ans.map[2][2]=1;
    if(n<=2)
        return 0*printf("1\n");
    n-=2;
    while(n)
    {
        if(n&1)
            ans=ans*base;
        base=base*base;
        n>>=1;
    }
    Matrix now(2,1);
    now.map[1][1]=now.map[2][1]=1;
    //ans.show();
    ans=ans*now;
    //now.show();
    printf("%d\n",ans.map[1][1]);
    return 0;
}
int main()
{
    #ifdef test
    #endif
    //freopen("a.in","r",stdin);
    while(~scanf("%d%d%d",&a,&b,&n))
    {
        if(!a && !b && !n)
            break;
        work(); 
    }
    return 0;
}