Run Code
|
API
|
Code Wall
|
Users
|
Misc
|
Feedback
|
Login
|
Theme
|
Privacy
|
Patreon
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.
Web Browser History
Binary Search
RegexMatch
without HLD range Quey can be handled by just using segment tree on the FLATTENED TREE (euler tour)
cppPyGuessTheNum2
Elevator
sheetal
Avoiding visited networked paths
merge-sort
Couting number of substring occurances in C++
Please log in to post a comment.