Run Code
|
API
|
Code Wall
|
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
Factorial Inv wip
Listas enlazadas - merge
new
idfc
K edit distance
1163. Last Substring in Lexicographical Order
on_off
Networked path_dp
Shuffle algorithm
max_size()_30-Seconds-of-C++