CF662C Binary Table

CF662C Binary Table

洛谷CF662C Binary Table

题目大意

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

$1\le n\le 20,1\le m\le 10^5$

题解

前置知识：快速沃尔什变换（$FWT$）

我们将每一列看作一种状态，则总共有$m$种状态。

设$a_i$表示状态$i$出现的次数，$b_i$表示$i$的二进制位中$0$的位数和$1$的位数的最小值。

设$f_k$表示翻转状态为$k$时的答案，则

$$f_k=\sum _{i=0}^{2^n-1}{a}_i\times b_{i\oplus k}$$

变换得

$$f_k=\sum _{i\oplus j=k}{a}_i\times b_j$$

这就是异或卷积，直接用$FWT$即可。

时间复杂度为$O(n\cdot 2^n)$。

code

#include<bits/stdc++.h>
using namespace std;
int n,m,v[100005],cnt[1<<20];
long long ans=1e18,a[1<<20],b[1<<20],c[1<<20];
int gt(){
	char ch=getchar();
	while(ch!='0'&&ch!='1') ch=getchar();
	return ch-'0';
}
void fwt(long long *w,int fl){
	for(int s=2;s<=1<<n;s<<=1){
		int mid=s>>1;
		for(int v=0;v<1<<n;v+=s){
			for(int i=0;i<mid;i++){
				long long t1=w[v+i],t2=w[v+mid+i];
				w[v+i]=t1+t2;
				w[v+mid+i]=t1-t2;
				if(fl==-1){
					w[v+i]/=2;
					w[v+mid+i]/=2;
				}
			}
		}
	}
}
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			int t=gt();
			v[j]|=(t<<i-1);
		}
	}
	for(int i=1;i<1<<n;i++){
		cnt[i]=cnt[i-(i&(-i))]+1;
		b[i]=min(cnt[i],n-cnt[i]);
	}
	for(int i=1;i<=m;i++) ++a[v[i]];
	fwt(a,1);fwt(b,1);
	for(int i=0;i<1<<n;i++){
		c[i]=a[i]*b[i];
	}
	fwt(c,-1);
	for(int i=0;i<1<<n;i++){
		ans=min(ans,c[i]);
	}
	printf("%lld",ans);
	return 0;
}