HDU4549

hdu4549.cpp

#include <cstdio>
#include <ctime>
#include <cstdlib>
#include <iostream>
#include <cstring>
#include <vector>
#include <fstream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <string>
#define MAX(a,b) (a>b?a:b)
#define sd(x) scanf("%d",&x)
#define sdd(a,b) scanf("%d%d",&a,&b)
#define sddd(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define slflf(x,y) scanf("%lf%lf",&x,&y)
#define abs(x) (x<0?(-x):x)
#define MAX(a,b) (a>b?a:b)
#define MIN(a,b) (a<b?a:b)
using namespace std;

const long long mod  = 1000000006;


long long quickMul(long long a,long long b)
{
    long long ans = 0;
    while(b>0)
    {
        if (b&1)
        {
            ans=(a+ans)%mod;
        }
        a = (a+a)%mod;
        b>>=1;
    }
    return ans;
}

class matrix
{
    //[ a  b ]
    //[ c  d ]
public:
    long long a, b, c, d;
    matrix(long long ma,long long mb,long long mc, long long md)
    {
        a = ma;
        b = mb;
        c = mc;
        d = md;
    }

    matrix operator * (matrix bm)
    {
        return matrix ((quickMul(a,bm.a)+quickMul(b,bm.c))%mod,(quickMul(a,bm.b)+quickMul(b,bm.d))%mod,\
                       (quickMul(c,bm.a)+quickMul(d,bm.c))%mod,(quickMul(c,bm.b)+quickMul(d,bm.d))%mod);
    }

};

long long quickM(long long base , int n)
{
    long long ans=1;
    while(n)
    {
        if (n&1) ans=ans*base%(mod+1);
        base=base*base%(mod+1);
        n>>=1;
    }
    return ans;
}


matrix quickM(int n)
{
    matrix base(1,1,1,0),ans(1,0,0,1);
    while(n)
    {
        if (n&1)
        {
            ans = ans * base;
        }
        base = base * base;
        n>>=1;
    }
    return ans;
}


int main()
{
    long long a,b;
    int n;
    while(cin >> a >> b >> n)
    {
        if (n==0)
        {
            printf("%d\n",a);
            continue;
        }
        if (n==1)
        {
            printf("%d\n",b);
            continue;
        }
        matrix fn = quickM(n-1);
        long long sum1 = quickM(a,fn.c);
        long long sum2 = quickM(b,fn.a);
        long long ans = sum1*sum2%(mod+1);
        cout << ans << endl;
    }
    return 0;
}