Nth term of a recurrence relation generated by two given arrays | C # 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 readonly 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 readonly 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
using System ; class GFG { static int mod = ( int ) ( 1e9 + 7 ) ; static int [ , ] T = new int [ 2000 , 2000 ] ; static int [ , ] result = new int [ 2000 , 2000 ] ; static void mul_2 ( int K ) { int [ , ] temp = new int [ K + 1 , K + 1 ] ; for ( int i = 1 ; i <= K ; i ++ ) { for ( int j = 1 ; j <= K ; j ++ ) { for ( int k = 1 ; k <= K ; k ++ ) { temp [ i , j ] = ( temp [ i , j ] + ( T [ i , k ] * T [ k , j ] ) % mod ) % mod ; } } } for ( int i = 1 ; i <= K ; i ++ ) { for ( int j = 1 ; j <= K ; j ++ ) { T [ i , j ] = temp [ i , j ] ; } } } static void mul_1 ( int K ) { int [ , ] temp = new int [ K + 1 , K + 1 ] ; for ( int i = 1 ; i <= K ; i ++ ) { for ( int j = 1 ; j <= K ; j ++ ) { for ( int k = 1 ; k <= K ; k ++ ) { temp [ i , j ] = ( temp [ i , j ] + ( result [ i , k ] * T [ k , j ] ) % mod ) % mod ; } } } for ( int i = 1 ; i <= K ; i ++ ) { for ( int j = 1 ; j <= K ; j ++ ) { result [ i , j ] = temp [ i , j ] ; } } } static void matrix_pow ( int K , int n ) { for ( int i = 1 ; i <= K ; i ++ ) { for ( int 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 /= 2 ; } } static int NthTerm ( int [ ] F , int [ ] C , int K , int n ) { for ( int i = 1 ; i <= K ; i ++ ) T [ i , K ] = C [ K - i ] ; for ( int i = 1 ; i <= K ; i ++ ) T [ i + 1 , i ] = 1 ; matrix_pow ( K , n ) ; int answer = 0 ; for ( int i = 1 ; i <= K ; i ++ ) { answer += F [ i - 1 ] * result [ i , 1 ] ; } Console . Write ( answer + " STRNEWLINE " ) ; return 0 ; } public static void Main ( String [ ] args ) { int [ ] F = { 1 , 2 , 3 } ; int [ ] C = { 1 , 1 , 1 } ; int K = 3 ; int N = 10 ; NthTerm ( F , C , K , N ) ; } }