代码模板-矩阵

矩阵用二维数组存储，$n \times n$ 方阵乘法的时间复杂度为 $O(n^3)$。带模数的版本配合快速幂可以在 $O(n^3 \log k)$ 的时间内求出矩阵幂，是矩阵加速线性递推的基础板子。

代码风格约定：模板统一写 int。竞赛时若有必要（乘积溢出、指数达到 $10^{12}$ 级别等），直接在全局写 #define int long long，省去逐个改类型的时间。

矩阵乘法

const int N = 105;
int n, m, k, a[N][N], b[N][N], c[N][N];

for (int i = 0; i < n; i++)          // 枚举 C 的行
    for (int l = 0; l < m; l++)      // 枚举相乘的位置
        for (int j = 0; j < k; j++)  // 枚举 C 的列
            c[i][j] += a[i][l] * b[l][j];

循环顺序对速度影响很大：求和下标 $k$ 放外层、$j$ 放最内层（如 $k,i,j$ 或 $i,k,j$），不要按 $i,j,k$ 把 $k$ 放最内层——$B[k][j]$ 按列跳跃访问会明显变慢。

矩阵快速幂

const int MAXN = 105, MOD = 1e9 + 7;

struct Matrix {
    int n;
    int a[MAXN][MAXN];
    Matrix(int n = 0) : n(n) { memset(a, 0, sizeof(a)); }

    static Matrix identity(int n) {      // 单位矩阵 I
        Matrix I(n);
        for (int i = 0; i < n; i++) I.a[i][i] = 1;
        return I;
    }

    Matrix operator*(const Matrix &B) const {
        Matrix C(n);
        for (int i = 0; i < n; i++)
            for (int k = 0; k < n; k++) {
                if (!a[i][k]) continue;  // 跳过 0，减少无效乘法
                int t = a[i][k];
                for (int j = 0; j < n; j++)
                    C.a[i][j] = (C.a[i][j] + t * B.a[k][j]) % MOD;
            }
        return C;
    }
};

Matrix mt_qmi(Matrix base, int p) {      // base 的 p 次幂
    Matrix ans = Matrix::identity(base.n);
    while (p) {
        if (p & 1) ans = ans * base;
        base = base * base;
        p >>= 1;
    }
    return ans;
}

循环按 $i, k, j$ 枚举，把 $A_{i,k}$ 提出后固定整行累加。最内层枚举 $j$ 时 $B$ 的行与 $C$ 的行都是沿行连续访问，缓存友好；切勿把求和下标 $k$ 放在最内层，$B[k][j]$ 按列跳跃访问会明显变慢。初始答案为单位矩阵 $I$（$A^0 = I$，类比整数快速幂初始值为 $1$）。指数达到 $10^{12}$ 级别或模数乘法有溢出风险时，不必逐个改类型，按全局约定直接 #define int long long。

定长最短路

const int MAXN = 205;
const int INF = 0x3f3f3f3f;

struct Mat {
    int n;
    int a[MAXN][MAXN];
    Mat(int n = 0) : n(n) { memset(a, 0x3f, sizeof(a)); }  // 初始化为 INF

    Mat operator*(const Mat &B) const {  // (min, +) 广义乘法
        Mat C(n);
        for (int i = 0; i < n; i++)
            for (int k = 0; k < n; k++) {
                if (a[i][k] == INF) continue;
                for (int j = 0; j < n; j++)
                    if (B.a[k][j] != INF)
                        C.a[i][j] = min(C.a[i][j], a[i][k] + B.a[k][j]);
            }
        return C;
    }
};

Mat mt_qmi(Mat base, int p) {            // (min, +) 意义下的 p 次幂
    Mat ans(base.n);
    for (int i = 0; i < base.n; i++) ans.a[i][i] = 0;  // 单位元：0 条边
    while (p) {
        if (p & 1) ans = ans * base;
        base = base * base;
        p >>= 1;
    }
    return ans;
}

$G[i][j]$ 存"走恰好 1 条边"的最短距离：有边存最小边权（重边取最小），无边存 $+\infty$，对角线保持 $+\infty$。$(G^{\odot k})_{a,b}$ 即 $a \to b$ 恰好走 $k$ 条边的最短路，时间复杂度 $O(n^3 \log k)$。

两个易错点：① 对角线若设成 $0$，相当于加入"原地停留"的假边，“恰好 $k$ 条边"会退化成"不超过 $k$ 条边”；② 累乘器的单位元是对角线为 $0$、其余为 $+\infty$ 的"0 条边"矩阵，不是全 $0$ 矩阵。

相关笔记：【线性代数】矩阵学习笔记