Difference between revisions of "Matrix Fundamentals"

From EOJ Wiki
Jump to navigation Jump to search
(Created page with "<syntaxhighlight lang='cpp'> struct Mat { static const LL M = 2; LL v[M][M]; Mat() { memset(v, 0, sizeof v); } void eye() { FOR (i, 0, M) v[i][i] = 1; } LL...")
 
Line 10: Line 10:
 
         const Mat& A = *this;
 
         const Mat& A = *this;
 
         Mat ret;
 
         Mat ret;
         FOR (i, 0, M)
+
         for (int i = 0; i < M; ++i)
             FOR (j, 0, M)
+
             for (int j = 0; j < M; ++j)
                 FOR (k, 0, M)
+
                 for (int k = 0; k < M; ++k)
 
                       ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % MOD;
 
                       ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % MOD;
 
         return ret;
 
         return ret;
Line 25: Line 25:
 
         const Mat& A = *this;
 
         const Mat& A = *this;
 
         Mat ret;
 
         Mat ret;
         FOR (i, 0, M)
+
         for (int i = 0; i < M; ++i)
             FOR (j, 0, M)
+
             for (int j = 0; j < M; ++j)
 
                 ret[i][j] = (A[i][j] + B[i][j]) % MOD;
 
                 ret[i][j] = (A[i][j] + B[i][j]) % MOD;
 
         return ret;
 
         return ret;
 
     }
 
     }
 
     void prt() const {
 
     void prt() const {
         FOR (i, 0, M)
+
         for (int i = 0; i < M; ++i)
             FOR (j, 0, M)
+
             for (int j = 0; j < M; ++j)
 
                 printf("%lld%c", (*this)[i][j], j == M - 1 ? '\n' : ' ');
 
                 printf("%lld%c", (*this)[i][j], j == M - 1 ? '\n' : ' ');
 
     }
 
     }
 
};
 
};
 
</syntaxhighlight>
 
</syntaxhighlight>

Revision as of 07:33, 22 March 2018

struct Mat {
    static const LL M = 2;
    LL v[M][M];
    Mat() { memset(v, 0, sizeof v); }
    void eye() { FOR (i, 0, M) v[i][i] = 1; }
    LL* operator [] (LL x) { return v[x]; }
    const LL* const operator [] (LL x) const { return v[x]; }
    Mat operator * (const Mat& B) {
        const Mat& A = *this;
        Mat ret;
        for (int i = 0; i < M; ++i)
            for (int j = 0; j < M; ++j)
                 for (int k = 0; k < M; ++k)
                      ret[i][j] = (ret[i][j] + A[i][k] * B[k][j]) % MOD;
        return ret;
    }
    Mat pow(LL n) const {
        Mat A = *this, ret; ret.eye();
        for (; n; n >>= 1, A = A * A)
            if (n & 1) ret = ret * A;
        return ret;
    }
    Mat operator + (const Mat& B) {
        const Mat& A = *this;
        Mat ret;
        for (int i = 0; i < M; ++i)
            for (int j = 0; j < M; ++j)
                 ret[i][j] = (A[i][j] + B[i][j]) % MOD;
        return ret;
    }
    void prt() const {
        for (int i = 0; i < M; ++i)
            for (int j = 0; j < M; ++j)
                 printf("%lld%c", (*this)[i][j], j == M - 1 ? '\n' : ' ');
    }
};