Nth term of a recurrence relation generated by two given arrays | Python3 program for the above approach ; Declare T [ ] [ ] as global matrix ; Result matrix ; Function to multiply two matrices ; Create an auxiliary matrix to store elements of the multiplication matrix ; Iterate over range [ 0 , K ] ; Update temp [ i ] [ j ] ; Update the final matrix ; Function to multiply two matrices ; Create an auxiliary matrix to store elements of the multiplication matrix ; Iterate over range [ 0 , K ] ; Update temp [ i ] [ j ] ; Update the final matrix ; Function to calculate matrix ^ n using binary exponentaion ; Initialize result matrix and unity matrix ; Function to calculate nth term of general recurrence ; Fill T [ ] [ ] with appropriate value ; Function Call to calculate T ^ n ; Calculate nth term as first element of F * ( T ^ n ) ; Print the result ; Driver Code ; Given Initial terms ; Given coefficients ; Given K ; Given N ; Function Call
mod = 1e9 + 7 NEW_LINE T = [ [ 0 for x in range ( 2000 ) ] for y in range ( 2000 ) ] NEW_LINE result = [ [ 0 for x in range ( 2000 ) ] for y in range ( 2000 ) ] NEW_LINE def mul_2 ( K ) : NEW_LINE INDENT temp = [ [ 0 for x in range ( K + 1 ) ] for y in range ( K + 1 ) ] NEW_LINE for i in range ( 1 , K + 1 ) : NEW_LINE INDENT for j in range ( 1 , K + 1 ) : NEW_LINE INDENT for k in range ( 1 , K + 1 ) : NEW_LINE INDENT temp [ i ] [ j ] = ( ( temp [ i ] [ j ] + ( T [ i ] [ k ] * T [ k ] [ j ] ) % mod ) % mod ) NEW_LINE DEDENT DEDENT DEDENT for i in range ( 1 , K + 1 ) : NEW_LINE INDENT for j in range ( 1 , K + 1 ) : NEW_LINE INDENT T [ i ] [ j ] = temp [ i ] [ j ] NEW_LINE DEDENT DEDENT DEDENT def mul_1 ( K ) : NEW_LINE INDENT temp = [ [ 0 for x in range ( K + 1 ) ] for y in range ( K + 1 ) ] NEW_LINE for i in range ( 1 , K + 1 ) : NEW_LINE INDENT for j in range ( 1 , K + 1 ) : NEW_LINE INDENT for k in range ( 1 , K + 1 ) : NEW_LINE INDENT temp [ i ] [ j ] = ( ( temp [ i ] [ j ] + ( result [ i ] [ k ] * T [ k ] [ j ] ) % mod ) % mod ) NEW_LINE DEDENT DEDENT DEDENT for i in range ( 1 , K + 1 ) : NEW_LINE INDENT for j in range ( 1 , K + 1 ) : NEW_LINE INDENT result [ i ] [ j ] = temp [ i ] [ j ] NEW_LINE DEDENT DEDENT DEDENT def matrix_pow ( K , n ) : NEW_LINE INDENT for i in range ( 1 , K + 1 ) : NEW_LINE INDENT for j in range ( 1 , K + 1 ) : NEW_LINE INDENT if ( i == j ) : NEW_LINE INDENT result [ i ] [ j ] = 1 NEW_LINE DEDENT DEDENT DEDENT while ( n > 0 ) : NEW_LINE INDENT if ( n % 2 == 1 ) : NEW_LINE INDENT mul_1 ( K ) NEW_LINE DEDENT mul_2 ( K ) NEW_LINE n //= 2 NEW_LINE DEDENT DEDENT def NthTerm ( F , C , K , n ) : NEW_LINE INDENT for i in range ( 1 , K + 1 ) : NEW_LINE INDENT T [ i ] [ K ] = C [ K - i ] NEW_LINE DEDENT for i in range ( 1 , K + 1 ) : NEW_LINE INDENT T [ i + 1 ] [ i ] = 1 NEW_LINE DEDENT matrix_pow ( K , n ) NEW_LINE answer = 0 NEW_LINE for i in range ( 1 , K + 1 ) : NEW_LINE INDENT answer += F [ i - 1 ] * result [ i ] [ 1 ] NEW_LINE DEDENT print ( int ( answer ) ) NEW_LINE DEDENT if __name__ == " _ _ main _ _ " : NEW_LINE INDENT F = [ 1 , 2 , 3 ] NEW_LINE C = [ 1 , 1 , 1 ] NEW_LINE K = 3 NEW_LINE N = 10 NEW_LINE NthTerm ( F , C , K , N ) NEW_LINE DEDENT