题解 CF662C 【Binary Table】

Description

有一个 n行 m 列的表格，每个元素都是 0/1 ，每次操作可以选择一行或一列，把 0/1翻转，即把 0换为 1，把 1换为 0。请问经过若干次操作后，表格中最少有多少个 1。

$n\le20,m\le 10^5$

Solution

n很小，我们可以考虑状压n，表示第i列的状态。

对于行的反转，我们也可以状压。

用 $0/1$ 表示当前这一行反转或未反转。

对于一个状态为i的列，当反转情况为k时，它当前列的状态为 $i\oplus k$ 。

可以用 $ans_k$ 记录当前反转状态为k的答案。

$f_i$ 表是列状态为i的的行数。

那么我们如何体现每一列的反转呢？

注意到，对于一列的反转，它的 $0$ 变为 $1$，$1$ 变为 $0$。

所以只要将列状态为i的0/1个数取min，便完成了列的反转。

记 $g_j$ 表示状态为j的0/1个数取min的结果。

那么有

$ans_k=\sum_if_i\times g_{i\oplus k}$

令 $j=i\oplus k$，则有 $k=i\oplus j$。

所以：

$ans_k=\sum_{i\oplus j=k}f_i\times g_j$

这就是异或卷积了，直接FWT就好。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define int long long
const int N=(1<<20)+9,M=1e5+9;
int n,m,f[N],g[N],a[M],num[N];
char s[M];

inline void FWT(int *f,int flag)
{
	for(int mid=2,k=1;mid<=n;mid<<=1,k<<=1)
		for(int i=0;i<n;i+=mid)
			for(int j=0;j<k;j++)
				f[i+j]+=f[i+j+k],
				f[i+j+k]=f[i+j]-f[i+j+k]-f[i+j+k],
				f[i+j]/=flag,f[i+j+k]/=flag;
}

signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
	{
		scanf("%s",s+1);
		for(int j=1;j<=m;j++)
			if(s[j]=='1') 
				a[j]|=(1<<i-1);
	}
	for(int i=1;i<=m;i++) f[a[i]]++;
	for(int i=0;i<(1<<n);i++) num[i]=num[i>>1]+(i&1);
	for(int i=0;i<(1<<n);i++) g[i]=min(num[i],n-num[i]);//体现出对某一列的反转
	n=(1<<n);
	FWT(f,1),FWT(g,1); 
	for(int i=0;i<n;i++) f[i]*=g[i];
	FWT(f,2);
	int ans=1e15;
	for(int i=0;i<n;i++)
		ans=min(ans,f[i]);
	printf("%lld",ans);
	return 0;
}