【CF662C】Binary Table（FWT）

【CF662C】Binary Table（FWT）

题面

洛谷
CF
翻译：
有一个(n*m)的表格((n<=20,m<=10^5))，
每个表格里面有一个(0/1)，
每次可以将一行或者一列的(01)全部翻转
回答表格中最少有多少个(1)

题解

发现(n)很小，(m)很大
状压是跑不掉了
如果我们确定翻转哪些行，那么答案唯一确定（贪心的选每一列中(0/1)的较小值）
相同的列显然可以合并，
把每一列按照(01)状压，记(a[i])为状态为(i)的列的个数
记(f[i])表示翻转状态为(i)的那些行的结果
假设翻转的行为(S)，这一列的状态为(i)，显然最终就变成了(ioplus S)
而对于每一列的任意一种状态(i)
答案显然是(min(Numberof(0),Numberof(1)))
预处理出来
这样子的话，我们就知道了(f[i]=sum_{joplus k=i}a[j]*b[k])
显然这是一个(xor)卷积，用(FWT)优化即可。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<queue>
using namespace std;
#define ll long long
#define RG register
inline int read()
{
    RG int x=0,t=1;RG char ch=getchar();
    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();
    if(ch=='-')t=-1,ch=getchar();
    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();
    return x*t;
}
int N,n,m;
ll a[1<<20],b[1<<20];
int g[21][100001];
void FWT(ll *P,int opt)
{
	for(int i=2;i<=N;i<<=1)
		for(int p=i>>1,j=0;j<N;j+=i)
			for(int k=j;k<j+p;++k)
			{
				ll x=P[k],y=P[k+p];
				P[k]=x+y;P[k+p]=x-y;
				if(opt==-1)P[k]/=2,P[k+p]/=2;
			}
}
int main()
{
	n=read();m=read();N=1<<n;
	char ch[100001];
	for(int i=1;i<=n;++i)
	{
		scanf("%s",ch+1);
		for(int j=1;j<=m;++j)g[i][j]=ch[j]-48;
	}
	for(int i=1;i<=m;++i)
	{
		int x=0;
		for(int j=1;j<=n;++j)x=(x<<1)|g[j][i];
		a[x]++;
	}
	for(int i=0;i<N;++i)b[i]=b[i>>1]+(i&1);
	for(int i=0;i<N;++i)b[i]=min(b[i],n-b[i]);
	FWT(a,1);FWT(b,1);
	for(int i=0;i<N;++i)a[i]*=b[i];
	FWT(a,-1);
	ll ans=n*m;
	for(int i=0;i<N;++i)ans=min(ans,a[i]);
	printf("%I64d
",ans);
	return 0;
}