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 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; int mod = 1e9 + 7 ; int T [ 2000 ] [ 2000 ] ; int result [ 2000 ] [ 2000 ] ; void mul_2 ( int K ) { int temp [ K + 1 ] [ K + 1 ] ; memset ( temp , 0 , sizeof temp ) ; 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 ] ; } } } void mul_1 ( int K ) { int temp [ K + 1 ] [ K + 1 ] ; memset ( temp , 0 , sizeof temp ) ; 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 ] ; } } } 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 ; } } 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 ] ; } cout << answer << endl ; return 0 ; } int main ( ) { int F [ ] = { 1 , 2 , 3 } ; int C [ ] = { 1 , 1 , 1 } ; int K = 3 ; int N = 10 ; NthTerm ( F , C , K , N ) ; return 0 ; }