题目链接

solution

因为(n)比较小，所以我们可以(2^n)枚举每一行是不是翻转。然后对于每一列答案就唯一了。

对于每一列状态压缩，用(b[i])表示(i)这个状态最小的(1)的个数(也就是这个状态里0和1更少的那个)。然后我们如果想把一列从状态(x)变成状态(y)，那么我们需要操作的行就是(xotimes y)。用(a[i])表示(i)这个状态的数量。用(ans_x)表示操作的行为(x)这个状态的时候的答案，就有(ans_x=sumlimits_{iotimes j=x}a[x]b[y])。用(fwt)优化即可。

code

/* * @author: wxyww * @date:   2020-04-26 10:45:28 * @last modified time: 2020-04-26 11:21:07 */ #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<algorithm> #include<queue> #include<vector> #include<ctime> using namespace std; typedef long long ll; const int n = 1 << 20; // #define int ll ll read() { 	ll x = 0,f = 1;char c = getchar(); 	while(c < '0' || c > '9') { 		if(c == '-') f = -1; c = getchar(); 	} 	while(c >= '0' && c <= '9') { 		x = x * 10 + c - '0'; c = getchar(); 	} 	return x * f; } char s[n]; int n,m;  void fwt(ll *a,int xs) { 	for(int i = 0;i < n;++i) { 		for(int j = 0;j < (1 << n);++j) { 			if((j >> i) & 1) continue; 			ll l = a[j],r = a[j | (1 << i)]; 			a[j] = l + r;a[j | (1 << i)] = l - r; 		} 	} 	if(xs == -1)  	for(int i = 0;i < (1 << n);++i) 		a[i] /= (1 << n); } ll a[n],cnt[n],a[n],b[n]; int main() { 	n = read(),m = read(); 	for(int i = 1;i <= n;++i) { 		scanf("%s",s + 1); 		for(int j = 1;j <= m;++j) 			a[j] = (a[j] << 1) | (s[j] - '0'); 	}  	for(int i = 1;i <= m;++i) a[a[i]]++;  	for(int i = 0;i < (1 << n);++i) { 		cnt[i] = (cnt[i >> 1]) + (i & 1); 		b[i] = min(cnt[i],n - cnt[i]); 	}  	fwt(b,1);fwt(a,1); 	for(int i = 0;i < (1 << n);++i) a[i] = a[i] * b[i]; 	fwt(a,-1);  	ll ans = n * m; 	for(int i = 0;i < (1 << n);++i) { 		ans = min(ans,a[i]); 	}  	cout<<ans; 	return 0; }