「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;
}