洛谷 CF662C Binary Table 题解
xiaoh 2020-5-19
题意
给定行列的二进制表(),每次可以翻转任意一行或一列(即与互换),且翻转次数没有限制.求反转后的最小数量.
题解
我们注意到小的离谱,而同时翻转行和列显然不容易处理,所以我们考虑枚举翻转哪些行,然后计算哪些列可行.
若我们记一行翻转为,不翻转为,则可以用一个整数压缩翻转状态.而对于每一列,我们也可以将其的状态压缩,记为,那么翻转行后的序列则为.接下来我们可以将视为常量,只考虑翻转列所带来的影响.而对于一个指定的翻转行后的列状态,该列的最小数量已经确定,为,其中为该列中的数量.我们将所有可能的种列状态可以达到的的的最小数目全部记录下来,不妨记这个数组为,然后暴力的枚举,得到以下转移方程
于是,你开心的获得了一个的算法并了本题
接下来考虑如何进行优化.我们可以在上面的转移方程上进行一点点小小的变形,变成如下的式子
似乎复杂度更高了别急,我们慢慢进行梳理,上述的式子实际上复杂度并不完美,因为它进行了好多次重复的计算.对于列状态相同的列,似乎它们的答案都是一模一样的,所以我们不妨一起处理.即为初始状态为的列的数量.那么就又可以变形了
好了,这个式子看起来就有它该有的样子了,我们再用比较高级的方法来表达一下上面这个式子(注意过程中用了一下异或的性质将一项移到了式子左边)
于是,我们愉快的使用做出了本题,时间复杂度.
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;
}