A RetroSearch Logo

Home - News ( United States | United Kingdom | Italy | Germany ) - Football scores

Search Query:

Showing content from https://TheAlgorithms.github.io/C-Plus-Plus/dc/d52/linear__recurrence__matrix_8cpp_source.html below:

TheAlgorithms/C++: math/linear_recurrence_matrix.cpp Source File

50template

<

typename

T =

int

64_t>

51

std::vector<std::vector<T>> matrix_multiplication(

52 const

std::vector<std::vector<T>>& _mat_a,

53 const

std::vector<std::vector<T>>& _mat_b,

const

int64_t mod = 1000000007) {

55

assert(_mat_a[0].size() == _mat_b.size());

56

std::vector<std::vector<T>> _mat_c(_mat_a.size(),

57

std::vector<T>(_mat_b[0].size(), 0));

61 for

(uint32_t i = 0; i < _mat_a.size(); ++i) {

62 for

(uint32_t j = 0; j < _mat_b[0].size(); ++j) {

63 for

(uint32_t k = 0; k < _mat_b.size(); ++k) {

66

(_mat_a[i][k] % mod * _mat_b[k][j] % mod) % mod) %

81template

<

typename

T =

int

64_t>

82bool

is_zero_matrix(

const

std::vector<std::vector<T>>& _mat) {

83 for

(uint32_t i = 0; i < _mat.size(); ++i) {

84 for

(uint32_t j = 0; j < _mat[i].size(); ++j) {

85 if

(_mat[i][j] != 0) {

103template

<

typename

T =

int

64_t>

104

std::vector<std::vector<T>> matrix_exponentiation(

105

std::vector<std::vector<T>> _mat, uint64_t

power

,

106 const

int64_t mod = 1000000007) {

112 if

(is_zero_matrix(_mat)) {

116

std::vector<std::vector<T>> _mat_answer(_mat.size(),

117

std::vector<T>(_mat.size(), 0));

119 for

(uint32_t i = 0; i < _mat.size(); ++i) {

120

_mat_answer[i][i] = 1;

125

_mat_answer = matrix_multiplication(_mat_answer, _mat, mod);

128

_mat = matrix_multiplication(_mat, _mat, mod);

154template

<

typename

T =

int

64_t>

155

T get_nth_term_of_recurrence_series(

156 const

std::vector<std::vector<T>>& _mat,

157 const

std::vector<std::vector<T>>& _base_cases, uint64_t nth_term,

158 bool

constant_or_sum_included =

false

) {

159

assert(_mat.size() == _base_cases.back().size());

165 if

(nth_term < _base_cases.back().size() - constant_or_sum_included) {

166 return

_base_cases.back()[nth_term - constant_or_sum_included];

172

std::vector<std::vector<T>> _res_matrix =

173

matrix_exponentiation(_mat, nth_term - _base_cases.back().size() +

174

1 + constant_or_sum_included);

180

std::vector<std::vector<T>> _res =

181

matrix_multiplication(_base_cases, _res_matrix);

183 return

_res.back().back();

207

std::vector<std::vector<int64_t>> fibonacci_matrix = {{0, 1}, {1, 1}},

208

fib_base_case = {{0, 1}};

210

assert(math::linear_recurrence_matrix::get_nth_term_of_recurrence_series(

211

fibonacci_matrix, fib_base_case, 11) == 89LL);

212

assert(math::linear_recurrence_matrix::get_nth_term_of_recurrence_series(

213

fibonacci_matrix, fib_base_case, 39) == 63245986LL);

230

std::vector<std::vector<int64_t>> tribonacci = {{0, 0, 1},

236

assert(math::linear_recurrence_matrix::get_nth_term_of_recurrence_series(

237

tribonacci, trib_base_case, 11) == 149LL);

238

assert(math::linear_recurrence_matrix::get_nth_term_of_recurrence_series(

239

tribonacci, trib_base_case, 36) == 615693474LL);

253

std::vector<std::vector<int64_t>> pell_recurrence = {{0, 1}, {1, 2}},

257

assert(math::linear_recurrence_matrix::get_nth_term_of_recurrence_series(

258

pell_recurrence, pell_base_case, 15) == 551614LL);

259

assert(math::linear_recurrence_matrix::get_nth_term_of_recurrence_series(

260

pell_recurrence, pell_base_case, 23) == 636562078LL);

283

std::vector<std::vector<int64_t>>

284

custom_recurrence = {{1, 0, 1}, {0, 0, 1}, {0, 1, 2}},

285

custom_base_case = {{7, 2, 2}};

287

assert(math::linear_recurrence_matrix::get_nth_term_of_recurrence_series(

288

custom_recurrence, custom_base_case, 10, 1) == 18493LL);

289

assert(math::linear_recurrence_matrix::get_nth_term_of_recurrence_series(

290

custom_recurrence, custom_base_case, 19, 1) == 51531251LL);

316

std::vector<std::vector<int64_t>> sum_fibo_recurrence = {{0, 1, 1},

319

sum_fibo_base_case = {

322

assert(math::linear_recurrence_matrix::get_nth_term_of_recurrence_series(

323

sum_fibo_recurrence, sum_fibo_base_case, 13, 1) == 609LL);

324

assert(math::linear_recurrence_matrix::get_nth_term_of_recurrence_series(

325

sum_fibo_recurrence, sum_fibo_base_case, 16, 1) == 2583LL);

353

std::vector<std::vector<int64_t>> tribonacci_sum = {{0, 0, 1, 1},

357

trib_sum_base_case = {{0, 0, 1, 1}};

360

assert(math::linear_recurrence_matrix::get_nth_term_of_recurrence_series(

361

tribonacci_sum, trib_sum_base_case, 18, 1) == 23249LL);

362

assert(math::linear_recurrence_matrix::get_nth_term_of_recurrence_series(

363

tribonacci_sum, trib_sum_base_case, 19, 1) == 42762LL);

static void test()

Self-test implementations.

int main()

Main function.

Functions for Linear Recurrence Matrix implementation.

RetroSearch is an open source project built by @garambo | Open a GitHub Issue

Search and Browse the WWW like it's 1997 | Search results from DuckDuckGo

HTML: 3.2 | Encoding: UTF-8 | Version: 0.7.4