Nth term of a recurrence relation generated by two given arrays | Javascript 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 ; Given Initial terms ; Given coefficients ; Given K ; Given N ; Function Call
let mod = ( 1e9 + 7 ) ; let T = new Array ( 2000 ) ; let result = new Array ( 2000 ) ; for ( let i = 0 ; i < 2000 ; i ++ ) { T [ i ] = new Array ( 2000 ) ; result [ i ] = new Array ( 2000 ) ; for ( let j = 0 ; j < 2000 ; j ++ ) { T [ i ] [ j ] = 0 ; result [ i ] [ j ] = 0 ; } } function mul_2 ( K ) { let temp = new Array ( K + 1 ) ; for ( let i = 0 ; i <= K ; i ++ ) { temp [ i ] = new Array ( K + 1 ) ; for ( let j = 0 ; j <= K ; j ++ ) { temp [ i ] [ j ] = 0 ; } } for ( let i = 1 ; i <= K ; i ++ ) { for ( let j = 1 ; j <= K ; j ++ ) { for ( let k = 1 ; k <= K ; k ++ ) { temp [ i ] [ j ] = ( temp [ i ] [ j ] + ( T [ i ] [ k ] * T [ k ] [ j ] ) % mod ) % mod ; } } } for ( let i = 1 ; i <= K ; i ++ ) { for ( let j = 1 ; j <= K ; j ++ ) { T [ i ] [ j ] = temp [ i ] [ j ] ; } } } function mul_1 ( K ) { let temp = new Array ( K + 1 ) ; for ( let i = 0 ; i <= K ; i ++ ) { temp [ i ] = new Array ( K + 1 ) ; for ( let j = 0 ; j <= K ; j ++ ) { temp [ i ] [ j ] = 0 ; } } for ( let i = 1 ; i <= K ; i ++ ) { for ( let j = 1 ; j <= K ; j ++ ) { for ( let k = 1 ; k <= K ; k ++ ) { temp [ i ] [ j ] = ( temp [ i ] [ j ] + ( result [ i ] [ k ] * T [ k ] [ j ] ) % mod ) % mod ; } } } for ( let i = 1 ; i <= K ; i ++ ) { for ( let j = 1 ; j <= K ; j ++ ) { result [ i ] [ j ] = temp [ i ] [ j ] ; } } } function matrix_pow ( K , n ) { for ( let i = 1 ; i <= K ; i ++ ) { for ( let j = 1 ; j <= K ; j ++ ) { if ( i == j ) result [ i ] [ j ] = 1 ; } } while ( n > 0 ) { if ( n % 2 == 1 ) mul_1 ( K ) ; mul_2 ( K ) ; n = parseInt ( n / 2 , 10 ) ; } } function NthTerm ( F , C , K , n ) { for ( let i = 1 ; i <= K ; i ++ ) T [ i ] [ K ] = C [ K - i ] ; for ( let i = 1 ; i <= K ; i ++ ) T [ i + 1 ] [ i ] = 1 ; matrix_pow ( K , n ) ; let answer = 0 ; for ( let i = 1 ; i <= K ; i ++ ) { answer += F [ i - 1 ] * result [ i ] [ 1 ] ; } document . write ( answer + " " ) ; return 0 ; } let F = [ 1 , 2 , 3 ] ; let C = [ 1 , 1 , 1 ] ; let K = 3 ; let N = 10 ; NthTerm ( F , C , K , N ) ;