CF662C Binary Table FWT
有一个 $n$ 行 $m$ 列的表格，每个元素都是 0/1，每次操作可以选择一行或一列，将 0/1 翻转，即 0 换为 1，1 换为 0.
求：经过若干次操作后，表格中最多有多少个 1.
数据范围：$1leqslant n leqslant 20,1leqslant m leqslant 10^5$
我们发现，如果只允许操作行/列的话这道题就非常好做了.
但是由于行翻转和列翻转是有交叉部分的，所以我们就很难去计算.
然后你发现一个特别好的性质就是虽然 $m$ 很大，但是 $n$ 很小.
所以我们可以考虑从 $n$ 入手.
一个最暴力的做法就是 $2^n$ 枚举每个行翻不翻转，然后依次枚举每个列，每个列的贡献就是0和1数量较小值.
这个时间复杂度是 $O(2^nm)$ 的.
我们将每一列的 0/1 状态都压成二进制 $sta[i]$，那么假如说行的翻转状态时 $p$ 的话第 $i$ 列的状态就是 $sta[i]igoplus p$
（ $igoplus $ 表示异或符号）
这个时候答案就是 $ans[p]=sum_{i igoplus j=p}cnt[i] imes val[j]$
这个 $val[j]$ 表示 $j$ 表示的二进制中 0 和 1 数量的较小值，$cnt[i]$ 表示初始状态下状态为 $i$ 的列的个数.
用 FWT 优化即可.
#include <cstdio>
#include <algorithm>
#define N 21
#define ll long long
#define setIO(s) freopen(s".in","r",stdin)
using namespace std;
char S[1<<N];
int lim,cnt[1<<N],g[1<<N];
ll a[1<<N],b[1<<N],ans=100000000;
int lowbit(int t) { return t&(-t); }
void FWT(ll *a,int opt)
{
int i,j,k;
for(i=1;i<lim;i<<=1)
{
for(j=0;j<lim;j+=i<<1)
{
for(k=0;k<i;++k)
{
ll x=a[j+k],y=a[j+k+i];
a[j+k]=x+y,a[j+k+i]=x-y;
if(opt==-1) a[j+k]/=2,a[j+k+i]/=2;
}
}
}
}
int main()
{
// setIO("input");
int i,j,n,m;
scanf("%d%d",&n,&m),lim=1<<n;
for(i=0;i<n;++i)
{
scanf("%s",S);
for(j=0;j<m;++j)
{
if(S[j]=='1') g[j]|=(1<<i);
}
}
for(i=0;i<m;++i) ++a[g[i]];
for(i=1;i<lim;++i) cnt[i]=cnt[i>>1]+(i&1);
for(i=0;i<lim;++i) b[i]=min(cnt[i],n-cnt[i]);
FWT(a,1),FWT(b,1);
for(i=0;i<lim;++i) a[i]*=b[i];
FWT(a,-1);
for(i=0;i<lim;++i) ans=min(ans,a[i]);
printf("%lld
",ans);
return 0;
}