UVA 12470 - Tribonacci

UVA Sep 01, 2020

Problem PDF

Solution:

/******************************************************************
***   Author        : Shipu Ahamed (Psycho Timekiller)          ***
***   E-mail        : [email protected]                   ***
***   University    : BUBT,Dept. of CSE                         ***
***   Team          : BUBT_HIDDEN                               ***
***   My Blog       : http://shipuahamed.blogspot.com           ***
***   Facebook      : http://www.facebook.com/DeesheharaShipu   ***
******************************************************************/
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define sc scanf
#define pf printf
#define ll long long
#define pi 2*acos(0.0)
#define ull unsigned long long
#define all(v) v.begin(),v.end()

#define sii(t) scanf("%d",&t)
#define sll(t) scanf("%lld",&t)
#define ssii(a,b) scanf("%d%d",&a,&b)
#define ssll(a,b) scanf("%lld%lld",&a,&b)
#define Case(no) printf("Case %d: ",++no)
#define P(a) printf("%d\n",a)
#define PL(a) printf("%lld\n",a)
#define PN(a) printf("%d",a)
#define PLN(a) printf("%lld",a)


#define ff first
#define se second
#define pb push_back
#define ST(v) sort(all(v))
#define gcd(a,b) __gcd(a,b)
#define lcm(a,b) (a*(b/gcd(a,b)))
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
#define maxall(v) *max_element(all(v))
#define minall(v) *min_element(all(v))
#define cover(a,d) memset(a,d,sizeof(a))
#define popcount(i) __builtin_popcount(i)                       //count one
#define input freopen("in.txt","r",stdin)
#define output freopen("out.txt","w",stdout)
#define un(v) ST(v), (v).earse(unique(all(v)),v.end())
#define common(a,b) ST(a), ST(b), a.erase(set_intersection(all(a),all(b),a.begin()),a.end())
#define uncommon(a,b) ST(a), ST(b), a.erase(set_symmetric_difference(all(a),all(b),a.begin()),a.end())

////============ CONSTANT ===============////
#define mx  (1000000)
#define inf (1<<30)                                            //infinity value
#define eps 1e-9
#define mod 1000000009
////====================================////

struct Matrix{
    long long arr[10][10];
};

Matrix MatrixMulti(Matrix a, Matrix b)
{
    Matrix result;
    int i,j,k;
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
        {
            result.arr[i][j]=0;
            for(k=0;k<3;k++)
                result.arr[i][j]+=(a.arr[i][k]*b.arr[k][j]);
            result.arr[i][j]=result.arr[i][j]%mod;
        }
    return result;
}

Matrix BigMod(Matrix a, long long n)
{
    Matrix ret;
    int i,j;
    for(i=0;i<3;i++)
        for(j=0;j<3;j++)
            {
                if(i==j)
                ret.arr[i][j]=1;
                else
                ret.arr[i][j]=0;
            }

    while(n)
    {
        if(n & 1)
    ret=MatrixMulti(a,a);
        a=MatrixMulti(a,a);
        n>>=1;
    }
    return a;
}

int main()
{
    Matrix mat,ans;
    long long n,m,i,j;
    cover(mat.arr,0);
//    for(i=0;i<3;i++)
//        for(j=0;j<3;j++)
//            mat.arr[i][j]=1;

    mat.arr[1][1]=mat.arr[2][1]=mat.arr[2][2]=mat.arr[0][2]=mat.arr[1][2]=1;
    while(cin>>n && n)
    {

            if(n==1)
            {
                cout<<"0"<
https://github.com/Shipu/OnlineJudgeProblemSolutionWithCPlusPlus/tree/master/uva/12470/Tribonacci.cpp

Tags

Shipu Ahamed

CSPO® | Partly Product, Project Manager and Partly Software Engineer.

Great! You've successfully subscribed.
Great! Next, complete checkout for full access.
Welcome back! You've successfully signed in.
Success! Your account is fully activated, you now have access to all content.