UVa 12470 Solution Explained

Problem Link :  12470 – Tribonacci

 

Solution :

If n = 1 0r 2 0r 3 return n-1;

else multiply the matrix M (n-3) times .

M = { {1,1,1},{1,0,0},{0,1,1}};

then multiply M with Matrix F.

F = { {2},{1},{0}};

F[0][0] is the required answer .(use modulo 1e9+7).

try it yourself . It will give you much more confidence.

 

My solution :

#include<iostream>
#include<vector>

using namespace std;

#define endl ‘\n’
#define Mod 1000000009

typedef long long int L;
void mul(L F[3][3],L M[3][3])
{
L x = (F[0][0]*M[0][0])%Mod + (F[0][1]*M[1][0])%Mod + (F[0][2]*M[2][0])%Mod;
L y = (F[0][0]*M[0][1])%Mod + (F[0][1]*M[1][1])%Mod + (F[0][2]*M[2][1])%Mod;
L z = (F[0][0]*M[0][2])%Mod + (F[0][1]*M[1][2])%Mod + (F[0][2]*M[2][2])%Mod;

L p = (F[1][0]*M[0][0])%Mod + (F[1][1]*M[1][0])%Mod + (F[1][2]*M[2][0])%Mod;
L q = (F[1][0]*M[0][1])%Mod + (F[1][1]*M[1][1])%Mod + (F[1][2]*M[2][1])%Mod;
L r = (F[1][0]*M[0][2])%Mod + (F[1][1]*M[1][2])%Mod + (F[1][2]*M[2][2])%Mod;

L m = (F[2][0]*M[0][0])%Mod + (F[2][1]*M[1][0])%Mod + (F[2][2]*M[2][0])%Mod;
L n = (F[2][0]*M[0][1])%Mod + (F[2][1]*M[1][1])%Mod + (F[2][2]*M[2][1])%Mod;
L o = (F[2][0]*M[0][2])%Mod + (F[2][1]*M[1][2])%Mod + (F[2][2]*M[2][2])%Mod;

F[0][0] = x , F[0][1]=y ,F[0][2]=z;
F[1][0] = p , F[1][1]=q ,F[1][2]=r;
F[2][0] = m , F[2][1]=n ,F[2][2]=o;
}

L tib(L n)
{
if(n<=3)
return n-1;
L F[3][3]= {{1,1,1},{1,0,0},{0,1,0}};
L M[3][3]= {{1,1,1},{1,0,0},{0,1,0}};

n = n-3-1;
//if(n%2==0)
while(n)
{
if(n&1)
mul(F,M);
n/=2;
mul(M,M);
}

F[0][0] = (F[0][0]*2)%Mod + (F[0][1]*1)%Mod ;
return F[0][0]%Mod;
}

int main()
{
//ios_base::sync_with_stdio(NULL);
//cin.tie(false);
L n;
while(cin>>n&&n!=0)
{
L ans = tib(n);
cout<<ans<<endl;
}
}

Thanks.

Mahmud