题目链接：「THUPC 2023」FRESHMAN DREAM
「THUPC 2023」FRESHMAN DREAM 题解
题目重述
给定一个 n×nn \times nn×n 的 01 矩阵 AAA，需要构造一个 01 矩阵 BBB，满足：
AB≡A⊙B(mod2)AB \equiv A \odot B \pmod 2 AB≡A⊙B(mod2)
其中 ABABAB 是普通矩阵乘法（模 2），⊙\odot⊙ 是逐元素乘积（Hadamard 积）。并且要求 BBB 中恰好有 kkk 个 1。若不存在则输出 -1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
解法分析
1. 条件转化
将 AB=A⊙BAB = A \odot BAB=A⊙B 写成元素形式，对任意 i,ji,ji,j：
∑l=1nAi,lBl,j≡Ai,jBi,j(mod2)\sum_{l=1}^n A_{i,l} B_{l,j} \equiv A_{i,j} B_{i,j} \pmod 2 l=1∑n Ai,l Bl,j ≡Ai,j Bi,j (mod2)
移项得：
∑l=1nAi,lBl,j+Ai,jBi,j≡0(mod2)\sum_{l=1}^n A_{i,l} B_{l,j} + A_{i,j} B_{i,j} \equiv 0 \pmod 2 l=1∑n Ai,l Bl,j +Ai,j Bi,j ≡0(mod2)
注意左边求和项中包含了 l=il=il=i 的项 Ai,iBi,jA_{i,i}B_{i,j}Ai,i Bi,j ，与最后的 Ai,jBi,jA_{i,j}B_{i,j}Ai,j Bi,j 合并：
∑l≠iAi,lBl,j+(Ai,i+Ai,j)Bi,j≡0(mod2)\sum_{l\neq i} A_{i,l} B_{l,j} + (A_{i,i}+A_{i,j})B_{i,j} \equiv 0 \pmod 2 l=i∑ Ai,l Bl,j +(Ai,i +Ai,j )Bi,j ≡0(mod2)
固定列 jjj，令向量 bj=(B1,j,B2,j,…,Bn,j)Tb_j = (B_{1,j}, B_{2,j}, \dots, B_{n,j})^Tbj =(B1,j ,B2,j ,…,Bn,j )T，则上式等价于：
(A+diag(A1,j,A2,j,…,An,j))⋅bj≡0(mod2)(A + \operatorname{diag}(A_{1,j}, A_{2,j}, \dots, A_{n,j})) \cdot b_j \equiv 0 \pmod 2 (A+diag(A1,j ,A2,j ,…,An,j ))⋅bj ≡0(mod2)
因此，对于每一列 jjj，bjb_jbj 必须是矩阵 Mj=A+diag(A1,j,…,An,j)M_j = A + \operatorname{diag}(A_{1,j},\dots,A_{n,j})Mj =A+diag(A1,j ,…,An,j ) 的零空间（核）中的一个向量。不同列之间相互独立，所以问题转化为：
* 对每个 j=1..nj=1..nj=1..n，求齐次线性方程组 Mjx=0M_j x = 0Mj x=0 的所有解向量；
* 从每个解空间中选择一个向量作为第 jjj 列，使得所有列中 1 的总数恰好为 kkk。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
2. 子问题求解
对于每个 jjj，矩阵 MjM_jMj 是 n×nn \times nn×n 的 01 矩阵。我们用高斯消元（异或消元）求出其行最简形，并找出自由变量。设自由变量个数为 fff，则解空间大小为 2f2^f2f。枚举所有自由变量的取值，即可得到所有解向量，并记录每个解的 1 的个数。
由于 AAA 是随机生成的，矩阵通常满秩（或接近满秩），所以 fff 很小，枚举是可行的。最坏情况下 fff 可能达到 nnn，但题目数据保证随机，且 n=100n=100n=100，即使最坏也可用优化，但实际运行良好。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
3. 全局背包合并
设 dp[i][s]dp[i][s]dp[i][s] 表示考虑了前 iii 列后，已经选用的 1 的总数为 sss 是否可行（0≤s≤k0 \le s \le k0≤s≤k）。
初始化 dp[0][0]=truedp[0][0] = \text{true}dp[0][0]=true。
对于第 iii 列，设其所有可能解向量的重量集合为 WiW_iWi （包含重复重量，去重或不区别均可，因为重量相同向量不同但只影响计数，我们只需知道重量存在即可，但后续回溯需要知道具体解，所以需要存储每个重量对应的一个解向量）。转移时：
dp[i][s]=⋁w∈Widp[i−1][s−w]dp[i][s] = \bigvee_{w \in W_i} dp[i-1][s-w] dp[i][s]=w∈Wi ⋁ dp[i−1][s−w]
同时记录转移来源（即当前列选择的重量 www），以便最后回溯构造矩阵。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
4. 回溯构造
若 dp[n][k]dp[n][k]dp[n][k] 为真，则从 i=ni=ni=n 开始，根据记录的 wiw_iwi 取出第 iii 列对应的解向量，然后 k←k−wik \leftarrow k - w_ik←k−wi ，继续向前。最终得到矩阵 BBB。
若 dp[n][k]dp[n][k]dp[n][k] 为假，输出 -1。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
复杂度分析
* 对每一列做高斯消元：O(n3)O(n^3)O(n3)，n=100n=100n=100，共 100 列，约 10810^8108 次位运算，但可用 bitset 优化，实际很快。
* 枚举解向量：O(2f⋅n)O(2^f \cdot n)O(2f⋅n)，由于随机矩阵满秩，fff 通常为 0 或很小，可忽略。
* DP：状态数 n×kn \times kn×k，转移时枚举重量集合，重量集合大小通常不大，总复杂度 O(n⋅k⋅avgW)O(n \cdot k \cdot \text{avgW})O(n⋅k⋅avgW)，可行。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
CODE:
其他人错误的方面：
1.高斯消元中主元列的选取和自由变量的处理；
2.分组背包的状态转移和回溯；
3.无解情况的判断。
