「Codeforces 662C」Binary Table

Codeforces 662C

题意

给出一个$n$行$m$列的$01$矩阵，可以任意次取反一行或一列，最小化矩阵中$1$的总数

$n\le20,m\le10^5$

---

分析

由于 $n$ 非常小，考虑状压，把 $m$ 列看成 $m$ 个 $n$ 位二进制数

同时也用一个 $n$ 位二进制数 $s$ 表示取反了的行

对于一个被表示为 $x$ 的列

• 若不选择取反，对答案的贡献是 ${\rm popcount}(x \oplus s)$

  其中 ${\rm popcount}(t)$ 表示 $t$ 二进制中为 $1$ 的位数，$\oplus$ 表示异或

• 若取反，则为 $n-{\rm popcount}(x \oplus s)$。

由于列之间是独立的，可以贪心选择，记 $g_i=\min({\rm popcount}(i),n-{\rm popcount}(i))$

记$f_i$表示$m$个数中$i$的数量

对于一种选择 $s$，答案是

$$\sum_{i=0}^{2^n-1}f_i\cdot g_{i \oplus s}$$

即

$$\sum_{i \oplus j=s}f_i\cdot g_j$$

使用 FWT 完成这个异或卷积

复杂度 $\mathcal O(nm+n\times 2^n)$

---

代码

#include<cstdio>
#include<algorithm>
#include<ctype.h>
#include<string.h>
#include<math.h>

using namespace std;
#define ll long long

inline char read() {
	static const int IN_LEN = 1000000;
	static char buf[IN_LEN], *s, *t;
	return (s == t ? t = (s = buf) + fread(buf, 1, IN_LEN, stdin), (s == t ? -1 : *s++) : *s++);
}
template<class T>
inline void read(T &x) {
	static bool iosig;
	static char c;
	for (iosig = false, c = read(); !isdigit(c); c = read()) {
		if (c == '-') iosig = true;
		if (c == -1) return;
	}
	for (x = 0; isdigit(c); c = read()) x = ((x + (x << 2)) << 1) + (c ^ '0');
	if (iosig) x = -x;
}

const int N = 22, M = 100005, K = 1<<20;
int n, m, a[M];
ll f[K], g[K];
inline void FWT(ll *f, int g, int len=1<<n){
	for(int i=1; i<len; i<<=1)
		for(int j=0; j<len; j+=i<<1)
			for(int k=j; k<j+i; ++k){
				ll x=f[k], y=f[k+i];
				f[k]=x+y, f[k+i]=x-y;
			}
	if(g==-1) for(int i=0; i<len; ++i) f[i]>>=n;
}
int main() {
	read(n), read(m);
	for(int i=0; i<n; ++i){
		char ch;
		while(isspace(ch=read()));
		for(int j=0; j<m; ++j, ch=read()) a[j]=a[j]<<1|(ch^'0');
	}
	for(int i=0; i<m; ++i) ++f[a[i]];
	for(int i=1; i<1<<n; ++i) g[i]=g[i^(i&-i)]+1;
	for(int i=0; i<1<<n; ++i) g[i]=min(g[i], n-g[i]);
	FWT(f, 1), FWT(g, 1);
	for(int i=0; i<1<<n; ++i) f[i]*=g[i];
	FWT(f, -1);
	int ans=1e9;
	for(int i=0; i<1<<n; ++i) ans=min(ans, (int)f[i]);
	return printf("%d", ans), 0;
}