「省选模拟赛」矩阵（matrix）

题目描述

有一个 $n*m$ 的 $01$ 矩阵，矩阵中 $k$ 个格子的数已经确定，你需要求出有多少种方案使得矩阵每行每列的异或和均为 $1$。对 $998244353$ 取模。

暴力自不必说

对于 $k = 0$ 的数据，如何做？

那么我们只要空出一列（或一行或是一行一列），让其它的格子随便填，因为不管怎么样，最后空出的这一列（行）总是可以将整行（列）的异或和变为 $1$

同理 $k <= m$ 的数据找出一个全空的列就好了

仿照 $Subtask 2$ 的思路，还是找出一个被限制的格子最少的列，令该列被限制的格子数为 $p$，考虑到 $k \le 10m$，故 $p \le 10$，那么对于其它列，只要关注这 $p$ 行以及它们本身列的异或和就好了

考虑使用 $DP$，设 $f_{i, j, k, state}$ 表示前 $i$ 列前 $j$ 行，目前该列的异或和为 $k$，那 $p$ 行的异或情况状压后为 $state$

复杂度 $O (nm2^{\frac{k}{m}})$

因为状态数太多，考虑能够直接计算的状态数就直接消去

对于除了那 $p$ 行以外还存在不被限制的格子的列，可以空出一个格子，然后其它格子随便填，然后将这些列删去

在删去上述列之前，还要计算它们对于行的贡献

假设在 $p$ 行的其中一行，在上述列中该行总共有 $k$ 个空格，那么同理还是只要留出一个空格其它随便填，故答案要算上 $2^{k - 1}$

那么对于未删去的列只需考虑那 $p$ 行就可以了（因为其它行一定是被限制的），然后仿照 $Subtask 3$ 做 $DP$ 即可

复杂度 $O (\frac{k^2}{nm}2^{\frac{k}{m}})$

感觉整题就是将空一行算异或的思想完全贯彻的说

至于代码，感觉理论上那些存在空格的行 $DP$ 之后不管取其异或为 $0$ 或 $1$ 都是可以的（可惜因为写到心态爆炸然后就放弃了代码的说

（至于考场上连 $Subtask 2$ 都没想出来，只是瞎打了 $k = 0$ 的规律而且还有可能错的我感觉我好菜啊