T4

20 分

暴力枚举每一行翻不翻转，然后计算答案即可，时间复杂度 $\mathcal{O}(m^22^n)$。

40 分

注意到如果钦定 $(i,j)$ 这个位置为 $1$，那么所有行的翻转情况就固定了！

这告诉我们什么呢？可以直接枚举钦定为 $1$ 的位置，然后确定所有行的翻转情况并计算答案。

枚举的位置数是 $\mathcal{O}(nm)$ 的，每次计算答案是 $\mathcal{O}(nm)$ 的，于是复杂度变成了 $\mathcal{O}(n^2m^2)$。

60 分

考虑优化上面的做法，可以发现每次重新计算答案将整个矩阵扫一遍是非常愚蠢的，将翻转情况与上次不同的行重新拿出来更新一下就行。时间复杂度 $\mathcal{O}(nm\max(n,m))$。

80 分

计算哪些列只有一个 $1$ 的过程可以使用 bitset 优化，时间复杂度 $\mathcal{O}(\frac{nm\max(n,m)}{w})$。

正解

真的有必要枚举位置后每次都去算一遍答案吗？

考虑如果 $(i,j),(k,l)\ (j\ne l)$ 两个位置能够同时为 $1$，那么两个位置所对应的行的翻转情况一定是一样的！

于是考虑对每个位置所对应的行的翻转情况进行 hash，一种行的翻转情况对应 hash 值计算方式如下：$\sum_{i=1}^n C_ip^i$，其中 $C_i$ 表示第 $i$ 行是否翻转，$p$ 为取的一个大质数。将所有的 hash 值丢进一个 map 里，相同值个数最多的就是答案。

时间复杂度 $\mathcal{O}(nm)$。