矩阵类模板

const int MAXN = 105;
const int MAXM = 105;
struct Martix
{
    int n, m;                    //n:矩阵行数         m:矩阵列数
    int a[MAXN][MAXM];
    void clear() {            //清空矩阵
        n = m = 0;
        memset(a, 0, sizeof(a));
    }
    Martix operator+(const Martix& b) const {
        Martix tmp;
        tmp.n = n; tmp.m = m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                tmp.a[i][j] = a[i][j] + b.a[i][j];
        return tmp;
    }
    Martix operator-(const Martix& b) const {
        Martix tmp;
        tmp.n = n; tmp.m = m;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                tmp.a[i][j] = a[i][j] - b.a[i][j];
        return tmp;
    }
    Martix operator*(const Martix& b) const {
        Martix tmp;
        tmp.clear();
        tmp.n = n; tmp.m = b.m;
        for (int i = 0; i < tmp.n; i++)
            for (int j = 0; j < tmp.m; j++) 
                for (int k = 0; k < m; k++) {
                    tmp.a[i][j] += a[i][k] * b.a[k][j];
                    tmp.a[i][j] %= mod;
                }
        return tmp;
    }
    Martix operator^(int x)const {
        Martix base, ans;
        base = *this; 
        ans.clear(); ans.m = ans.n = n;
        for (int i = 0; i < n; i++) ans.a[i][i] = 1;
        if (x == 0) return ans;
        if (x == 1) return base;
        while (x) {
            if (x & 1) ans = ans * base;
            base = base * base;
            x >>= 1;
        }
        return ans;
    }
};