Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
matrix_exponentiation.cpp File Reference

Matrix Exponentiation. More...

#include <iostream>
#include <vector>
Include dependency graph for matrix_exponentiation.cpp:

Macros

#define ll   int64_t
 
#define endl   std::endl
 
#define pb   push_back
 
#define MOD   1000000007
 

Functions

vector< vector< ll > > multiply (const vector< vector< ll >> &A, const vector< vector< ll >> &B)
 
vector< vector< ll > > power (const vector< vector< ll >> &A, ll p)
 
ll ans (ll n)
 
int main ()
 

Variables

ll mat_size
 
vector< llfib_b
 
vector< llfib_c
 

Detailed Description

Matrix Exponentiation.

The problem can be solved with DP but constraints are high.
\(a_i = b_i\) (for \(i <= k\))
\(a_i = c_1 a_{i-1} + c_2 a_{i-2} + ... + c_k a_{i-k}\) (for \(i > k\))
Taking the example of Fibonacci series, \(k=2\)
\(b_1 = 1,\; b_2=1\)
\(c_1 = 1,\; c_2=1\)
\(a = \begin{bmatrix}0& 1& 1& 2& \ldots\end{bmatrix}\)
This way you can find the \(10^{18}\) fibonacci numberMOD. I have given a general way to use it. The program takes the input of B and C matrix.

Steps for Matrix Expo

  1. Create vector F1 : which is the copy of B.
  2. Create transpose matrix (Learn more about it on the internet)
  3. Perform \(T^{n-1}\) [transpose matrix to the power n-1]
  4. Multiply with F to get the last matrix of size (1 \(\times\)k).

The first element of this matrix is the required result.

Macro Definition Documentation

◆ endl

#define endl   std::endl

shorthand definition for std::endl

◆ ll

#define ll   int64_t

shorthand definition for int64_t

◆ pb

#define pb   push_back

shorthand definition for int64_t

Function Documentation

◆ ans()

ll ans ( ll  n)

Wrapper for Fibonacci

Parameters
[in]n\(n^\text{th}\) Fibonacci number
Returns
\(n^\text{th}\) Fibonacci number
91  {
92  if (n == 0)
93  return 0;
94  if (n <= mat_size)
95  return fib_b[n - 1];
96  // F1
97  vector<ll> F1(mat_size + 1);
98  for (ll i = 1; i <= mat_size; i++) F1[i] = fib_b[i - 1];
99 
100  // Transpose matrix
102  for (ll i = 1; i <= mat_size; i++) {
103  for (ll j = 1; j <= mat_size; j++) {
104  if (i < mat_size) {
105  if (j == i + 1)
106  T[i][j] = 1;
107  else
108  T[i][j] = 0;
109  continue;
110  }
111  T[i][j] = fib_c[mat_size - j];
112  }
113  }
114  // T^n-1
115  T = power(T, n - 1);
116 
117  // T*F1
118  ll res = 0;
119  for (ll i = 1; i <= mat_size; i++) {
120  res = (res + (T[1][i] * F1[i]) % MOD) % MOD;
121  }
122  return res;
123 }

◆ main()

int main ( void  )

Main function

126  {
127  cin.tie(0);
128  cout.tie(0);
129  ll t;
130  cin >> t;
131  ll i, j, x;
132  while (t--) {
133  cin >> mat_size;
134  for (i = 0; i < mat_size; i++) {
135  cin >> x;
136  fib_b.pb(x);
137  }
138  for (i = 0; i < mat_size; i++) {
139  cin >> x;
140  fib_c.pb(x);
141  }
142  cin >> x;
143  cout << ans(x) << endl;
144  fib_b.clear();
145  fib_c.clear();
146  }
147  return 0;
148 }

◆ multiply()

vector<vector<ll> > multiply ( const vector< vector< ll >> &  A,
const vector< vector< ll >> &  B 
)

To multiply 2 matrices

Parameters
[in]Amatrix 1 of size (m \(\times\)n)
[in]Bmatrix 2 of size (p \(\times\)q)
Note
\(p=n\)
Returns
matrix of dimension (m \(\times\)q)
58  {
60  for (ll i = 1; i <= mat_size; i++) {
61  for (ll j = 1; j <= mat_size; j++) {
62  for (ll z = 1; z <= mat_size; z++) {
63  C[i][j] = (C[i][j] + (A[i][z] * B[z][j]) % MOD) % MOD;
64  }
65  }
66  }
67  return C;
68 }

◆ power()

vector<vector<ll> > power ( const vector< vector< ll >> &  A,
ll  p 
)

computing integer power of a matrix using recursive multiplication.

Note
A must be a square matrix for this algorithm.
Parameters
[in]Abase matrix
[in]pexponent
Returns
matrix of same dimension as A
76  {
77  if (p == 1)
78  return A;
79  if (p % 2 == 1) {
80  return multiply(A, power(A, p - 1));
81  } else {
82  vector<vector<ll>> X = power(A, p / 2);
83  return multiply(X, X);
84  }
85 }
Here is the call graph for this function:

Variable Documentation

◆ fib_b

vector<ll> fib_b

global vector variables used in the ans function.

Todo:
@stepfencurryxiao add documetnation

◆ mat_size

ll mat_size

global variable mat_size

Todo:
@stepfencurryxiao add documetnation
mat_size
ll mat_size
Definition: matrix_exponentiation.cpp:45
std::vector
STL class.
ans
ll ans(ll n)
Definition: matrix_exponentiation.cpp:91
multiply
vector< vector< ll > > multiply(const vector< vector< ll >> &A, const vector< vector< ll >> &B)
Definition: matrix_exponentiation.cpp:57
std::cout
endl
#define endl
Definition: matrix_exponentiation.cpp:36
fib_b
vector< ll > fib_b
Definition: matrix_exponentiation.cpp:50
power
vector< vector< ll > > power(const vector< vector< ll >> &A, ll p)
Definition: matrix_exponentiation.cpp:76
std::cin