Cpp update 1, C++ (gcc)

Cpp update 1

//-------------------------------------------------------------------------------------------------------------------------------
//g++  7.4.0 
//Base File           
//-------------------------------------------------------------------------------------------------------------------------------
/*                                                 ᕙ(  • ‿ •  )ᕗ Dire Wolf
                                              
                                                     ->Manan's Code Pad<-
                                            
Patience                                                                                                                  Bravery
                                                           
*/
//-------------------------------------------------------------------------------------------------------------------------------
//                                                     ¯\_(ツ)_/¯ <Code>
//-------------------------------------------------------------------------------------------------------------------------------

#include <bits/stdc++.h>
#define ll long long

using namespace std;

//Matrix Exponentiation
const long long M = 1000000007;
void multiply (vector<vector<ll>>&A, vector<vector<ll>>&B)
{
    int N=A.size();
    vector<vector<ll>>R(N,vector<ll>(N));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            R[i][j] = 0;
            
            for (int k = 0; k < N; k++)
            {
                R[i][j] = (R[i][j] + A[i][k] * B[k][j]) % M;
            }
        }
    }
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            A[i][j] = R[i][j];
        }
    }
}
void power_matrix (vector<vector<ll>>&A, int n)
{
    int N=A.size();
    vector<vector<ll>>B(N,vector<ll>(N));
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            B[i][j] = A[i][j];
        }
    }
    n = n - 1;
    while (n > 0)
    {
        if (n & 1)
            multiply (A, B);
        multiply (B,B);
        n = n >> 1;  
    }
}
// A = Coefficient Matrix, B = Base Matrix. 
// It returns the nth term of the recurrence relation formed from A and B in O(log n).
long long solve_recurrence (vector<vector<ll>>&A, vector<vector<ll>>&B, int n)
{
    int N=A.size();
    //Base Cases.
    if (n < N)
        return B[N - 1 - n][0];
    power_matrix (A, n - N + 1);
    long long result = 0;
    for (int i = 0; i < N; i++)
        result = (result + A[0][i] * B[i][0]) % M;
    return result;
}
//

int main()
{
    //std::cout << "Hello, world!\n";
      
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    vector<vector<ll>> A = {{2, 1, 3}, {1, 0, 0}, {0, 1, 0}};
    vector<vector<ll>> B = {{3}, {2}, {1}};
    int n=5;
    long long R_n = solve_recurrence (A, B, n);
    cout<<R_n;
    
    
      return 0;
}

//-------------------------------------------------------------------------------------------------------------------------------
//                                                          End
//-------------------------------------------------------------------------------------------------------------------------------


run \| edit \| history \| help	0

Please log in to post a comment.