洛谷 CF662C Binary Table 题解

洛谷 CF662C Binary Table 题解

xiaoh 2020-5-19

题意

给定nnmm列的二进制表(1n20,1m1051\leq n\leq 20,1\leq m\leq 10^5),每次可以翻转任意一行或一列(即0011互换),且翻转次数没有限制.求反转后11的最小数量.

题解

我们注意到nn小的离谱,而同时翻转行和列显然不容易处理,所以我们考虑枚举翻转哪些行,然后计算哪些列可行.

若我们记一行翻转为11,不翻转为00,则可以用一个整数xx压缩翻转状态.而对于每一列,我们也可以将其的状态压缩,记为sis_i,那么翻转行后的序列则为si  xor  xs_i\;xor\;x.接下来我们可以将xx视为常量,只考虑翻转列所带来的影响.而对于一个指定的翻转行后的列状态,该列11的最小数量已经确定,为min(num1,nnum1)min(num_1,n-num_1),其中num1num_1为该列中11的数量.我们将所有可能的2n2^n种列状态可以达到的的11的最小数目全部记录下来,不妨记这个数组为mpmp,然后暴力的枚举xx,得到以下转移方程::

ansx=i=1mmpsi  xor  xans_x=\sum_{i=1}^m mp_{s_i\; xor\; x}

于是,你开心的获得了一个O(2nm)O(2^nm)的算法并TLETLE了本题

接下来考虑如何进行优化.我们可以在上面的转移方程上进行一点点小小的变形,变成如下的式子::

ansx=j=02ni=1m  [j==yi  xor  x]  mpjans_x=\sum_{j=0}^{2^n}\sum_{i=1}^m\;[j==y_i\;xor\;x]\;mp_j

似乎复杂度更高了别急,我们慢慢进行梳理,上述的式子实际上复杂度并不完美,因为它进行了好多次重复的计算.对于列状态相同的列,似乎它们的答案都是一模一样的,所以我们不妨一起处理.即numinum_i初始状态为ii的列的数量.那么就又可以变形了::

ansx=j=02ni=02n  [j==i  xor  x]  numi×fjans_x=\sum_{j=0}^{2^n}\sum_{i=0}^{2^n}\;[j==i\;xor\;x]\;num_i\times f_j

好了,这个式子看起来就有它该有的样子了,我们再用比较高级的方法来表达一下上面这个式子(注意过程中用了一下异或的性质将一项移到了式子左边)::

ansx=i=j  xor  x  numi×fjans_x=\sum_{i=j\;xor\;x}\;num_i \times f_j

于是,我们愉快的使用FWTFWT做出了本题,时间复杂度O(2n)O(2^n).

Code

#include<bits/stdc++.h>
using namespace std;
template<typename T>
inline void read(T &x)
{
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9')
	{
		if(ch=='-') f=-1;
		ch=getchar();
}
	while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
	x*=f;
	return;
}	
template<typename T>
void write(T x)
{
	if(x<0) putchar('-'),x=-x;
	if(x>=10) write(x/10);
	putchar(x%10+'0');
	return;
}
const int MAXN=21,MAXM=100010;
const long long inf=999999999;
int n,m;
int a[MAXN][MAXM];
long long mp[1<<MAXN];
long long num[1<<MAXN];
inline long long count(register int x)
{
    register long long ret=0;
    while(x)
    {
        (x&1)&&ret++;
        x>>=1;
    }
    return ret;
}
long long ans[MAXN];
inline void FWT_xor(register long long *a,register int opt)
{
    for(register int i=1;i<(1<<n);i<<=1)
    for(register int j=0,p=i<<1;j<(1<<n);j+=p)
    for(register int k=0;k<i;++k)
    {
        register long long x=a[j+k],y=a[i+j+k];
        a[j+k]=x+y,a[i+j+k]=x-y;
        if(opt==-1) a[j+k]>>=1,a[i+j+k]>>=1;
    }
}
long long minn=inf;
int main()
{
    read(n),read(m);
    for(register int i=1;i<=n;++i)
    for(register int j=1;j<=m;++j) scanf("%1d",&a[i][j]);
    for(register int i=0;i<=(1<<n)-1;++i) mp[i]=min(count(i),n-count(i));
    for(register int j=1;j<=m;++j)
    {
        register int tmp=0;
        for(register int i=1;i<=n;++i)
        if(a[i][j]) tmp|=1<<(i-1);
        num[tmp]++;
    }
    FWT_xor(num,1),FWT_xor(mp,1);
    for(register int i=0;i<(1<<n);++i) ans[i]=num[i]*mp[i];
    FWT_xor(ans,-1);
    for(register int i=0;i<(1<<n);++i) minn=min(minn,ans[i]);
    write(minn),putchar('\n');
	return 0;
}