CODEWITHSUNDEEP
c++arraysloopsmatrixzero
Learning Equals Success
Learning Equals Success

Reputation: 194

How to raise a zero-one matrix to any power in C++?

I made a zero-one matrix with power 2. However, I want the code to be applied to any power the user enters. I tried several times, but it didn't work.

Here's a part of the code that would concern you.

Notes: Suppose the user has entered his (n*m) matrix which is "a", as n and m are equals and they are denoted by s. 

k=0;
for(int j=0; j<s; j++)
    for(int i=0; i<s; i++)
    {
        m[k]=0;

        for(int t=0; t<s; t++)
        m[k]+=a[j][t]*a[t][i];

        k++;
    }

Upvotes: 2

Views: 248

Answers (1)

Barish Namazov
Barish Namazov

Reputation: 340

Here is my implementation for matrix exponentiation:

struct matrix {
    intt m[K][K];
    matrix() {
        memset (m, 0, sizeof (m));
    }
    matrix operator * (matrix b) {
        matrix c = matrix();
        for (intt i = 0; i < K; i++) {
            for (intt k = 0; k < K; k++) {
                for (intt j = 0; j < K; j++) {
                    c.m[i][j] = (c.m[i][j] + m[i][k] * b.m[k][j]) % MOD;
                }
            }
        }
        return c;
    }
    matrix pow (intt n) {
        if (n <= 0) {
            return matrix();
        }
        if (n == 1) {
            return *this;
        }
        if (n % 2 == 1) {
            return (*this) * pow (n - 1);
        } else {
            matrix X = pow (n / 2);
            return X * X;
        }
    }
};

Upvotes: 3

Related Questions