题解 P9382 [THUPC 2023 决赛] Freshman Dream

· · 题解

根据矩阵乘法的式子 C_{i,j}=\sum_kA_{i,k}\times B_{k,j}，可以发现 B 的每一列都是独立的。假设我们正在处理第 p 列，根据题目所给的信息，列出如下方程：

\begin{cases} a_{1,1}b_{1,k}+a_{1,2}b_{2,k}+\cdots a_{1,n}b_{n,k}=a_{1,k}b_{1,k}\\ a_{2,1}b_{1,k}+a_{2,2}b_{2,k}+\cdots a_{2,n}b_{n,k}=a_{2,k}b_{2,k}\\ \ \vdots \\ a_{n,1}b_{1,k}+a_{n,2}b_{2,k}+\cdots a_{n,n}b_{n,k}=a_{n,k}b_{n,k}\\ \end{cases}

移项，写成增广矩阵：

\begin{bmatrix} a_{1,1}-a_{1,k} & a_{1,2} & \cdots & a_{1,n} & 0 \\ a_{2,1} & a_{2,2}-a_{2,k} & \cdots & a_{2,n} & 0 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ a_{n,1} & a_{n,2} & \cdots & a_{n,n}-a{n,k} & 0 \end{bmatrix}

设这个矩阵为 A。它最右边都是零，可以暂时不用管。对去掉最后一列的 A 矩阵进行高斯-约旦消元，可以得到线性基。这个线性基有如下性质：

  1. 如果 A_{i,i}=0，那么整行都是零。如果 A_{i,i}=1，那么 i 这一列只有 A_{i,i}=1。
  2. 对于任意一行 k，有等式 \sum_{i}A_{k,i}b_{k,i}=0。

由于数据随机，所以 A 矩阵的自由元（也就是全为零的行代表的元）很少。（证明见官方题解）而且，如果确定了所有自由元，那么其它元的取值都能够确定。（因为性质 2 的等式中至多只有一个非自由元）

暴力枚举自由元，就可以得到一组解。题目要求所有列中 1 的个数恰好等于 k，做一个背包即可。

Code