矩阵

矩阵计算

矩阵通常用二维数组表示, $matrix_{i,j}$ 表示第 $i$ 行，第 $j$ 列。

加减

只可针对同型矩阵，直接对应位置相加减。

$$\left[\begin{array}{l}a_1 & b_1 & c_1\\d_1 & e_1 & f_1\end{array}\right] \pm \left[\begin{array}{l}a_2 & b_2 & c_2\\d_2 & e_2 & f_2\end{array}\right]=\left[\begin{array}{l}a_1\pm a_2 & b_1\pm b_2 & c_1\pm c_2\\d_1\pm d_2 & e_1\pm e_2 & f_1\pm f_2\end{array}\right]$$

数乘

将 $k$ 分别乘以矩阵中每个元素。

$$k\left[\begin{array}{l}a & b & c\\d & e & f\\ g & h & i\end{array}\right]=\left[\begin{array}{l}ka & kb & kc\\kd & ke & kf\\ kg & kh & ki\end{array}\right]$$

乘法

要求： $A\times B$ , 要求 $A$ 的列数等于 $B$ 的行数。

$e.g.$ ：$A$ 的大小为 $m \times n$ , $B$ 的大小为 $n \times u$ , 二者乘积 $C=A\times B$ 的大小为 $m\times u$ 。

公式：$C[i,j] = \sum\limits_{k=1}^{n}A[i][k]\times B[k][j]$ 。

时间复杂度： $\mathcal O(n^3)$

for (int i = 1; i <= m; i ++)
	for (int j = 1; j <= u; j ++)
		for (int k = 1; k <= n; k ++)
			c[i][j] += a[i][k] * b[k][j];

注意：

• 矩阵乘法结合律：$(AB)C=A(BC)$
• 矩阵乘法分配律： $(A+B)C=AC+BC$
• BUT，矩阵乘法无交换律！！！

矩阵快速幂

对于一个 $N \times N$ 的矩阵 $A$ , 要求计算 $b$ 个 $A$ 相乘 的结果 $A^b$ ，此类问题可用快速幂计算。

时间复杂度：$\mathcal O(N^3logb)$

实数计算中有单位元1，矩阵乘法中也有单位矩阵 $E$ ( $E_{i,j} = [i==j]$ )

$$E =\left[\begin{array}{l}1 & 0 & \dots & 0\\0 & 1 & \dots & 0\\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1\end{array}\right]$$

const int MOD = 1e9 + 7;
struct MATRIX
{
    int N;
    vector<vector<int>> m;
    
    MATRIX(int N_) : N(N_) 
    {
        m.resize(N + 1);
        for (int i=1;i<=N;i++)
            m[i].resize(N + 1, 0);
    }
    
    void read()
    {
        for (int i=1;i<=N;i++)
            for (int j=1;j<=N;j++)
                cin >> m[i][j];
    }

    void print()
    {
        for (int i=1;i<=N;i++)
            for (int j=1;j<=N;j++)
                cout << m[i][j] << " \n"[j == N];
    }
};

MATRIX operator*(const MATRIX &a, const MATRIX &b)
{
    int N = a.N;
    MATRIX c(N);
    for (int i=1;i<=N;i++)
        for (int j=1;j<=N;j++)
            for (int k=1;k<=N;k++)
                c.m[i][j] = (c.m[i][j] + a.m[i][k] * b.m[k][j] % MOD) % MOD;
    return c;
}

MATRIX qpow(MATRIX &a, int b)
{
    int N = a.N;
    MATRIX ans(N);
    for (int i=1;i<=N;i++)    ans.m[i][i] = 1;	// 初始化，类似于普通快速幂的 ans = 1
    while (b)
    {
        if (b & 1)  ans = ans * a;
        a = a * a;
        b >>= 1;
    }
    return ans;
}

void solve()
{
    int n, m;   cin >> n >> m;
    MATRIX a(n);
    a.read();
    auto ans = qpow(a, 5);
    ans.print();
}

矩阵加速

在面对含有递推式的题目，数据范围过大时，直接递推会超时，常用矩阵快速幂加速递推。