1矩阵

1.1 基本矩阵运算

1.2 高斯消元

将矩阵左边消为单位矩阵

1.3 矩阵快速幂

1.1 1.2 1.3 归总代码如下：

struct Matrix
{
    int n, m;
    double a[MAXN][MAXN];

    void clear()
    {
        n = m = 0;
        memset(a, 0, sizeof(a));
    }

    void init(int t)
    {
        clear();
        n = m = t;
        for (int i = 1; i <= t; ++i)
            a[i][i] = 1;
    }
    Matrix operator + (const Matrix &b) const
    {
        Matrix tmp;
        tmp.n = n;
        tmp.m = m;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                tmp.a[i][j] = a[i][j] + b.a[i][j];
        return tmp;
    }

    Matrix operator - (const Matrix &b) const
    {
        Matrix tmp;
        tmp.n = n;
        tmp.m = m;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j)
                tmp.a[i][j] = a[i][j] - b.a[i][j];
        return tmp;
    }

    Matrix operator * (const Matrix &b) const
    {
        Matrix tmp;
        tmp.clear();
        tmp.n = n;
        tmp.m = b.m;
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= b.m; ++j)
                for (int k = 1; k <= m; ++k)
                    tmp.a[i][j] += a[i][k] * b.a[k][j];
        return tmp;
    }

    void gauss()
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = i; j <= n; ++j)
                if (fabs(a[j][i]) > eps)
                {
                    if (j == i)
                        break;
                    for (int k = i; k <= m; ++k)
                        swap(a[i][k], a[j][k]);
                    break;
                }
            for (int j = m; j >= i; --j)
                a[i][j] /= a[i][i];
            for (int j = 1; j <= n; ++j)
            {
                if (j == i || fabs(a[j][i]) < eps)
                    continue;
                double tmp = a[j][i] / a[i][i];
                for (int k = i; k <= m; ++k)
                    a[j][k] -= tmp * a[i][k];
            }
        }
    }

    Matrix pow(int t)
    {
        Matrix res;
        res.init(n);
        Matrix tmp = *this;
        while (t)
        {
            if (t & 1)
            {
                res = res * tmp;
            }
            tmp = tmp * tmp;
            t >>= 1;
        }
        return res;
    }

    void print()
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 1; j <= m; ++j)
                cout << a[i][j] << ' ';
            cout << endl;
        }
    }
};

1.4 矩阵求逆

增广矩阵法

用高斯消元

void matrix_inv(Matrix a)
{
    int n = a.n;
    b.n = b.m = n;
    a.gauss();
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            b.a[i][j] = a.a[i][j + n];
}