Please subscribe to the official Codeforces channel in Telegram via the link: https://t.me/codeforces_official. ×

Help! Strange Segmentation Fault Error for Recursive Matrix Fast Exponentiation

Revision en5, by duckladydinh, 2017-09-26 21:46:54

Hi friends,

During the implementation of matrix fast exponentiation, I have encountered a segmentation fault in the recursive approach. Even if I have managed to fix it by changing it to a loop, but I really want to know what is wrong with my code. I wonder if you can help me.

This is my recursive implementation. I cannot understand what is wrong with it. With n = 1, it is fine, but if n is greater than 1, then segmentation fault.


const int N = 100; struct Matrix { llnum c[N+N][N+N]; int n = 0, m = 0; Matrix(int _n, int _m) { n = _n, m = _m; for (int i = 0; i < n; ++i) { for (int j = 0; j < m; ++j) { c[i][j] = 0; } } } void out() { REP(i, n) { REP(j, m) { cout << c[i][j] << " \n"[j+1 == m]; } } cout << "\n"; } }; Matrix fast_pow(Matrix A, int n) { if (n == 0) return ident(A.m); if (n == 1) return A; Matrix E = fast_pow(A, (n/2)); if (n % 2 == 1) { return mul(E, A); } return E; }

Thank you.

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en5 English duckladydinh 2017-09-26 21:46:54 391
en4 English duckladydinh 2017-09-25 06:26:19 79
en3 English duckladydinh 2017-09-25 06:25:24 1 Tiny change: 'ow(Matrix &A, int n) ' -> 'ow(Matrix A, int n) '
en2 English duckladydinh 2017-09-25 06:23:38 2 Tiny change: 'with it.\n~~~~~\n\' -> 'with it.\n\n~~~~~\n\'
en1 English duckladydinh 2017-09-25 06:22:34 671 Initial revision (published)