P15093 [UOI 2025 II Stage] Odd Rows

一次，s1mple 找到了著名的问题解决者 Kostya，对他说： **如果你想变得更强，就需要持续练习。这里有一个用于训练的问题：** 给定一个大小为 $n \times m$ 的矩阵 $a$（$n$ 为行数，$m$ 为列数），其中每个元素要么是 $0$，要么是 $1$。已知每列恰好包含 $c_i$ 个 $1$。每列内的元素可以自由排列。目标是最大化包含奇数个 $1$ 的行数，并找出这样的一个矩阵。 Kostya 默默点头，坐到桌边开始工作，深知每一次练习都让他更接近精通。 Kostya 没能解决这个问题，现在请你帮他解决它。 **如果你只找出数量而不输出矩阵，可以获得部分分数。详情见下文。**

- 第一行包含两个整数 $n$ 和 $m$（$1 \le n \cdot m \le 10^6$）——矩阵的维度。 - 第二行包含 $m$ 个整数 $c_1, c_2, \dots, c_m$（$0 \le c_i \le n$）——每列中 $1$ 的数量。

- 第一行输出一个整数 $t$（$0 \leq t \leq n$）——矩阵中具有奇数和的行数。 - 接下来的 $n$ 行，每行输出 $m$ 个整数 $a_{ij}$（$0 \leq a_{ij} \leq 1$）——矩阵的元素。

在第一个示例中，第一列和第三列至少在 $4$ 个位置相交，这意味着如果只有这两列，我们将有 $4$ 个偶数和行。但由于还有两列各有一个 $1$，我们可以将其中两行转换为奇数和，因此最优答案是 $6$ 个奇数和行。 在第二个示例中，我们可以忽略第二列和第四列，因为它们没有 $1$，这意味着它们不会改变任何行的奇偶性。第一列和第三列至少在 $2$ 行相交，意味着至少有 $2$ 行是偶数和，因此答案是 $2$。 在第三个示例中，答案是 $7$，因为存在一个满足条件且具有 $7$ 个奇数和行的矩阵，并且不存在多于 $7$ 个奇数和行的矩阵。 ### 评分细则 - （$10$ 分）：$n, m \le 5$； - （$8$ 分）：矩阵中 $1$ 的总数不超过 $n$； - （$20$ 分）：每列中 $1$ 的数量不超过 $n/2$； - （$14$ 分）：$n, m \le 50$； - （$14$ 分）：$n \le 3\,000$； - （$14$ 分）：$n \cdot m \le 3\cdot10^5$； - （$20$ 分）：无额外限制。 对于每个测试组，如果你为该组中每个测试输出了正确的 $t$，你可以获得该组一半的分数。 注意，要获得部分分数，你需要输出正确的 $t$ 并且： - 要么不输出其他内容，即只输出 $t$，不输出矩阵； - 要么输出一个完整的由 $0$ 和 $1$ 组成的矩阵，该矩阵不必正确。例如，可以是一个全零矩阵。 如果你只输出部分行、或输出过多行、或输出非 $0$ 非 $1$ 的数字等，你将获得 $0$ 分。 翻译由 DeepSeek V3 完成