自动搬运

查看原文

来自洛谷，原作者为

	Graphcity 循此苦旅，终抵繁星。

搬运于2025-08-24 22:47:51，当前版本为作者最后更新于2023-06-10 15:09:38，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

根据矩阵乘法的式子 $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