human
Matrix Exponentiation | A utility function to multiply two matrices a [ ] [ ] and b [ ] [ ] . Multiplication result is stored back in b [ ] [ ].
Creating an auxiliary matrix to store elements of the multiplication matrix.
storing the multiplication result in a [ ] [ ].
Updating our matrix.
Function to compute F raise to power n - 2..
Multiply it with initial values i . e with F ( 0 ) = 0 , F ( 1 ) = 1 , F ( 2 ) = 1.
Multiply it with initial values i . e with F ( 0 ) = 0 , F ( 1 ) = 1 , F ( 2 ) = 1.
Return n 'th term of a series defined using below recurrence relation. f(n) is defined as f(n) = f(n-1) + f(n-2) + f(n-3), n>=3 Base Cases : f(0) = 0, f(1) = 1, f(2) = 1.
Driver code"
Solution in Python:
assistant
#Here is code to matrix Exponentiation and the other steps required.
 def multiply ( a , b ) :
	mul = [ [ 0 for x in range ( 3 ) ] for y in range ( 3 ) ] ;
	for i in range ( 3 ) :
		for j in range ( 3 ) :
			mul [ i ] [ j ] = 0 ;
			for k in range ( 3 ) :
				mul [ i ] [ j ] += a [ i ] [ k ] * b [ k ] [ j ] ;
	for i in range ( 3 ) :
		for j in range ( 3 ) :
		a [ i ] [ j ] = mul [ i ] [ j ] ;
	return a ;
def power ( F , n ) :
	M = [ [ 1 , 1 , 1 ] , [ 1 , 0 , 0 ] , [ 0 , 1 , 0 ] ] ;
	if ( n == 1 ) :
		return F [ 0 ] [ 0 ] + F [ 0 ] [ 1 ] ;
	power ( F , int ( n / 2 ) ) ;
	F = multiply ( F , F ) ;
	if ( n % 2 != 0 ) :
		F = multiply ( F , M ) ;
	return F [ 0 ] [ 0 ] + F [ 0 ] [ 1 ] ;
def findNthTerm ( n ) :
	F = [ [ 1 , 1 , 1 ] , [ 1 , 0 , 0 ] , [ 0 , 1 , 0 ] ] ;
	return power ( F , n - 2 ) ;
n = 5 ;
print ( " F ( 5 ) ▁ is " , findNthTerm ( n ) ) ;