F

n(<=20)行m(<=1e5)列的01矩阵
现在可以使任意行/列的数字反转
求最后最少的1

DP

$d[k][msk]$ 表示所有行xor msk,有k个1的个数(即表示反转哪些列)

$d[k][msk] = \frac{1}{k}\sum_{p=0}^{n-1} d[k-1][msk\text{ xor }2^p] - d[k-2][msk] + d[k-3][msk\text{ xor }2^p]$
$d[k][msk] = \frac{1}{k}\sum_{p=0}^{n-1}\sum_{f=1}^{k} (-1)^{f-1} d[k-f][msk\text{ xor }(2^p *(f \pmod 2))]$

然而复杂度为 $O(n^32^n)$ 还是不够,接着化简这个式子

令$k = k-2$

$d[k-2][msk] = \frac{1}{k-2}\sum_{p=0}^{n-1}\sum_{f=1}^{k-2} (-1)^{f-1} d[k-2-f][msk\text{ xor }(2^p *(f \pmod 2))]$
$d[k-2][msk] = \frac{1}{k-2}\sum_{p=0}^{n-1}\sum_{f=3}^{k} (-1)^{f-1} d[k-f][msk\text{ xor }(2^p *(f \pmod 2))]$

再将这个式子回带得到

$d[k][msk] = \frac{1}{k}((k-2-n)d[k-2][msk] + \sum_{p=0}^{n-1} d[k-1][msk\text{ xor }2^p])$

最后答案为 $min(\sum_{k=0}^{n-1} min(n-k,k)d[k][msk])$

复杂度 $O(n^22^n)$

FWT

我们令$A_i = cnt_i$,令$B_i = min(popcount(i),n-popcount(i))$,求一个xor卷积

其中$C_k = \sum_{i\text{ xor }j = k} A_iB_j$
根据xor的性质 $i\text{ xor }k = j$,因此每个k对应一种msk

复杂度 $O(2^nlog(2^n))$ ($O(n2^n)$)