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