【CF662C】Binary Table

题目

题目链接：https://codeforces.com/problemset/problem/662/C
有一个 (n) 行 (m) 列的表格，每个元素都是 (0/1) ，每次操作可以选择一行或一列，把 (0/1) 翻转，即把 (0) 换为 (1) ，把 (1) 换为 (0) 。请问经过若干次操作后，表格中最少有多少个 (1) 。
(nleq 20,mleq 10^5)。

思路

由于行数很小，所以我们考虑枚举每一行是否翻转，然后显然每一列就互相独立了。假设我们确定了翻转行的集合 (S)，答案就是

[sum^{m}_{i=1}min(mathrm{bit}_{S mathrm{xor} a_i},n-mathrm{bit}_{S mathrm{xor} a_i}) ]

其中 (mathrm{bit}_x) 表示 (x) 二进制下 (1) 的数量。(a_i) 表示第 (i) 列组成的二进制数的十进制表示。
我们预处理出 (f_i) 表示数值为 (i) 的列的数量，(g_i) 表示 (i) 二进制下 (0) 的数量和 (1) 的数量的较小值。
那么如果我们枚举翻转的行的集合为 (S)，答案为

[sum^{2^{n}-1}_{i=0}f_i imes g_{i mathrm{xor} S} ]

那么我们设 (h_s) 表示翻转集合为 (s) 时 (1) 最少的数量，

[h_s=sum_{i mathrm{xor} j=s}f_i imes g_j ]

FWT 板子。时间复杂度 (O(n(2^n+m)))。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1100010,M=22;
int n,m,lim,a[M][N];
ll ans,f[N],g[N];

void FWT(ll *f,int typ)
{
	for (int k=1;k<lim;k<<=1)
		for (int i=0;i<lim;i+=(k<<1))
			for (int j=0;j<k;j++)
			{
				ll x=f[i+j],y=f[i+j+k];
				f[i+j]=(x+y)>>typ;
				f[i+j+k]=(x-y)>>typ;
			}
}

int main()
{
	scanf("%d%d",&n,&m);
	for (int i=1;i<=n;i++)
		for (int j=1;j<=m;j++)
			scanf("%1d",&a[i][j]);
	for (int i=1;i<=m;i++)
	{
		int s=0;
		for (int j=1;j<=n;j++)
			s=s|(a[j][i]<<j-1);
		f[s]++;
	}
	lim=(1<<n);
	for (int i=1;i<lim;i++) g[i]=g[i-(i&-i)]+1;
	for (int i=1;i<lim;i++) g[i]=min(g[i],n-g[i]);
	FWT(f,0); FWT(g,0);
	for (int i=0;i<lim;i++) f[i]=f[i]*g[i];
	FWT(f,1);
	ans=2e18;
	for (int i=0;i<lim;i++)
		ans=min(ans,f[i]);
	printf("%lld",ans);
	return 0;
}