Codeforces

分析

设 $S_i$ 表示第 $i$ 列的状态，$F_i$ 表示 $i$ 状态翻转或不翻转最少能有多少个 $1$ 。

首先考虑一个暴力：枚举翻转哪几行。那么答案就是 $\displaystyle\min_{X}\left\{\sum_{i=1}^mF_{S_i\oplus X}\right\}$。

里面考虑枚举 $S_i\oplus X$，那么答案就是 $\displaystyle\min_{X}\left\{\sum_{i=1}^m\sum_{Y=0}^{2^n-1}\left[S_i\oplus X=Y\right]F_Y\right\}$。

设 $G_i$ 表示有多少列的状态为 $i$ 。那么答案可以表示成 $\displaystyle\min_X\left\{\sum_{S=0}^{2^n-1}\sum_{Y=0}^{2^n-1}\left[S\oplus X=Y\right]F_Y\times G_S\right\}$。

我们把 $S\oplus X=Y$ 两端同时异或 $S$ ，那么这个条件就变成了 $S\oplus Y=X$，里面的东西就变成了 $\displaystyle\sum_{S\oplus Y=X}F_Y\times G_S$，可以发现是一个异或卷积的形式。

那么直接构造出 $F$ 和 $G$ ，然后 FWT 求出它们的异或卷积，取其所有项中的最小值即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

const int N=20+10,M=100000+10;

int n,m,a[N][M];
int S[M],F[1<<20],G[1<<20];

inline void FWT(int* A,int n,int op) {
    for (re int i=1;i<n;i<<=1)
        for (re int j=0;j<n;j+=(i<<1))
            for (re int k=0;k<i;++k) {
                int x=A[j+k],y=A[j+k+i];
                A[j+k]=x+y,A[j+k+i]=x-y;
                if (op==-1) A[j+k]/=2,A[j+k+i]/=2;
            }
}

signed main() {
    scanf("%lld%lld",&n,&m); int lim=1<<n;
    for (re int i=1;i<=n;++i)
        for (re int j=1;j<=m;++j)
            scanf("%1lld",&a[i][j]);
    for (re int i=1;i<=m;++i)
        for (re int j=1;j<=n;++j)
            if (a[j][i]) S[i]|=1<<(j-1);
    for (re int i=1;i<lim;++i) F[i]=F[i>>1]+(i&1);
    for (re int i=1;i<lim;++i) F[i]=min(F[i],n-F[i]);
    for (re int i=1;i<=m;++i) ++G[S[i]];
    FWT(F,lim,1),FWT(G,lim,1);
    for (re int i=0;i<lim;++i) F[i]*=G[i];
    FWT(F,lim,-1);
    int ans=2e9;
    for (re int i=0;i<lim;++i) ans=min(ans,F[i]);
    printf("%lld\n",ans);
    return 0;
}