题解

问题分析

本题包含两个独立子问题，均涉及有限域上线性空间的基的计数，核心是利用线性代数中的矩阵行列式工具求解组合方案数。

子问题一：$\mathrm{GF}(3)$ 上的基方案数

问题描述：给定 $n$ 个 $\mathrm{GF}(3)$ 上的 $m$ 维向量，其张成空间 $V$ 的维数为 $m$，求从 $n$ 个向量中选出 $m$ 个线性无关向量（构成 $V$ 的基）的方案数，结果对 $3$ 取模。

核心思路：
利用矩阵行列式的性质刻画线性无关向量组的计数。具体构造如下：

1. 构造 $m \times n$ 矩阵 $A$，其中第 $i$ 列是第 $i$ 个向量（按分量存储在 $\mathrm{GF}(3)$ 中）。
2. 计算 $A$ 与 $A$ 的转置矩阵 $A^T$ 的乘积 $C = A \cdot A^T$（$C$ 是 $m \times m$ 矩阵）。
3. $C$ 的行列式模 $3$ 即为所求方案数。

原理：矩阵 $A \cdot A^T$ 的行列式在 $\mathrm{GF}(3)$ 上等价于所有 $m$ 阶子式的平方和（模 $3$），而每个非零 $m$ 阶子式对应一组线性无关的向量，其总和模 $3$ 恰好是基的方案数。

子问题二：$\mathrm{GF}(2)$ 上带颜色的基方案数

问题描述：给定 $n$ 个 $\mathrm{GF}(2)$ 上的 $m$ 维向量，每个向量有颜色 $c_i$（$1 \leq c_i \leq m$），其张成空间 $V$ 的维数为 $m$。求从每种颜色中恰好选一个向量，构成 $V$ 的基的方案数，结果对 $2$ 取模。

核心思路：
通过构造两个矩阵的乘积，利用行列式模 $2$ 的性质计数。具体构造如下：

1. 构造 $m \times n$ 矩阵 $A$，第 $i$ 列是第 $i$ 个向量（$\mathrm{GF}(2)$ 中分量）。
2. 构造 $n \times m$ 矩阵 $B$，其中 $B[i][c_i] = 1$（其余位置为 $0$），即第 $j$ 列对应颜色 $j$ 的所有向量。
3. 计算 $A \cdot B$（$m \times m$ 矩阵）的行列式模 $2$，即为所求方案数。

原理：$A \cdot B$ 的第 $j$ 列是颜色 $j$ 的所有向量在 $\mathrm{GF}(2)$ 中的和（异或）。其行列式模 $2$ 等价于所有“每种颜色选一个向量”的组合中，线性无关组的数量的奇偶性，即方案数模 $2$。

代码解析

1. 矩阵操作：定义 Matrix 类封装矩阵乘法和行列式计算。

   • 矩阵乘法：按有限域运算规则实现（模 $3$ 或 $2$）。
   • 行列式计算：通过高斯消元将矩阵化为上三角矩阵，行列式为对角线元素乘积，同时考虑行交换的符号（模对应素数）。

2. 子问题适配：

   • 对于 $\mathrm{taskid}=1$：构造矩阵 $A$ 和 $A^T$，计算乘积的行列式模 $3$。
   • 对于 $\mathrm{taskid}=2$：构造矩阵 $A$ 和 $B$，计算乘积的行列式模 $2$。

复杂度分析

• 时间复杂度：矩阵乘法和高斯消元的时间复杂度均为 $O(m^3)$（因 $n \leq 500$，矩阵乘积的主导项为 $m^3$），适用于 $m \leq 500$ 的约束。
• 空间复杂度：$O(m^2 + nm)$，用于存储矩阵 $A$、$B$ 及中间结果。

综上，算法通过将组合计数问题转化为有限域上的矩阵行列式计算，高效求解了两个子问题，充分利用了线性代数与有限域的性质。