FWT & FMT

CF662C

首先有一个 \(\mathcal O(2^nm)\) 的做法。

枚举每一行是否反转的状态 \(s\)，记 \(g_i=\min(\operatorname{popcount}(i),n-\operatorname{popcount}(i))\)，\(t_i\) 表示第 \(i\) 列的状态。

则答案为 \(\min_s{\sum_{i=1}^m g_{s\operatorname{xor} t_i}}\)。

发现这个东西很难处理，记 \(f_i\) 表示 \(t_j=i\) 的个数。

则答案为 \(\min_s{\sum_{i=1}^{2^n-1} g_{s\operatorname{xor} i}f_i}\)。

发现有 \(s \operatorname{xor} i \operatorname{xor} i=0\)，原式可以写作：

显然是一个标准的 FWT 形式。

直接做就可以了。