description
给定一个 \(n\times m(n\le 20,m\leq 10^5 )\) 的 01 矩阵，你可以把若干行的 01 反转，再把若干列的 01 反转。求若干操作后可能的最少的 1 的个数。
solution
显然操作相当于每行每列要么取反一次，要么不取反。
行数比较少，我们可以用一个 \(n\) 位二进制数描述对行的取反操作。如果我们已经确定了如何给行数取反，只需要考虑每一列是否取反。设 \(c_i\) 表示反转行后第 \(i\) 列剩余的 1 的个数，那么第 \(i\) 列对答案的贡献就是 \(\min(c_i,n-c_i)\)。于是我们得到了一个 \(O(2^nm)\) 的算法。
对于一个列，其状态可以用一个 \(n\) 为二进制数描述。对于每一个状态 \(s\)，它对答案的贡献都是固定的，记作 \(p_s=\min(\texttt{popcount}(s),n-\texttt{popcount}(s))\)。
设一个取反操作的状态是 \(s_1\)，原矩阵中某一列的状态是 \(s_2\)，那么它对答案的贡献就是 \(p_{s1~\texttt{xor}~s2}\)。
设原矩阵有 \(cnt_s\) 列的状态为 \(cnt\)，我们可以写出答案计算式，\(ans=\min\limits_{i=0}^{2^n-1}\sum p_j\times cnt_{i~\texttt{xor}~j}\)
一次 FWT 求出所有内层 \(\sum\)，然后枚举行操作状态 \(i\) 即可。
时间复杂度 \(O((2^n+m)n)\)