题解：P14476 矩阵绘画

· · 题解

我们考虑如何判定一个 01 矩阵 A 能否被画出来。

可以这样描述绘画方案：如果矩阵里一个位置是选行画出来的，则把这个 1 改为右箭头；如果一个位置是选列画出来的，则把这个位置的 1 改为下箭头；0 改为空位。这个只包含箭头（和空位）的矩阵就可以描述方案。我们称箭头和空位组成的 B 是 A 对应的方案矩阵。

可以发现：只要我们确定了 B_{1,1}，那么剩余位置就是确定的。 如果 B_{1,1} 是右箭头，则意味着每一行是否被画只需要看 A_{i,1} 的值。除了前 a_1 列必定没被画，后面每一列是否被画也只需要看 A_{1,j} 的值。如果 B_{1,1} 是下箭头，情况类似。如果 B_{1,1} 是空，仍然是上面两种情况的特例，且更为简单。

因此，每个合法方案要么 1 种操作方法，要么 2 种操作方法（只有当 A_{1,1}=1 且 B_{1,1} 两种方向都可行的情况下）。我们直接容斥：方案数等于合法的 B 矩阵数量减去对应两个 B 的 A 矩阵数量。

对于任何 B 矩阵都存在一条唯一的从左上角只向右和向下的分界线使得分界线左下方全是右箭头，而右上方全是下箭头，且分界线不能再往左下方空位调整（分界线每个向下拐弯的位置都紧贴着一个右箭头）。

证明：如果一个下箭头在右箭头的左下方，则下箭头上方和右箭头左边相交位置会冲突，所以不可能有这样的情况。所以，一定存在这样的分界线。只要分界线有某个向下拐弯的位置是空位，就往下调整，这样总能得到唯一的满足上文条件的分界线。

所以合法的 B 矩阵数量只要先枚举 B_{1,1} 再逐步递推分界线计算即可，f[i,j] 表示分界线走到 (i,j) 时的方案数，容易转移。时间复杂度为 O(n^2)。

现在我们只要统计对应两个 B 的 A 矩阵数量。这种矩阵分为两部分：左上角的 b_1 行 a_1 列子矩阵是固定的。而从 (b_1,a_1) 这个位置往右下方走仍然存在一条如前文所述性质的分界线。所以同样方法递推即可。时间复杂度仍然是 O(n^2)。

综上，整个问题的时间复杂度是 O(n^2)