C++(g++ 7.5.0) 解法, 执行用时: 140ms, 内存消耗: 19120K, 提交时间: 2022-10-26 22:59:15

#include<bits/stdc++.h>
using namespace std;

using ll = long long;
using pii = pair<ll,ll>;

void fwht_xor(vector<ll>&A, int inv){
    int n = A.size();
    for(int step = 1; step < n ; step *= 2){
        for(int i = 0 ; i < n ; i += 2*step){
            for(int j = i ; j < i + step ; j ++){
                auto &u = A[j], &v = A[j+step];
                tie(u,v) = pii(u+v, u-v);
            }
        }
    }
    if(inv) for(int i = 0 ; i < n ; i ++) A[i] /= n;
}


int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);

    int n,m; cin >> n >> m;
    int len = (1<<n);

    vector<ll>cnt(len, 0), f(len, 0);
    vector<string>a(n);
    for(int i = 0 ; i < n ; i ++){
        cin >> a[i];
    }
    for(int i = 0 ; i < m ; i ++){
        int now = 0;
        for(int j = 0 ; j < n ; j ++){
            if(a[j][i]=='1') now |= (1<<j);
        }
        cnt[now]++;
    }
    for(int i = 0 ; i < len ; i ++){
        f[i] = __builtin_popcount(i);
        f[i] = min(f[i], n-f[i]);
    }

    fwht_xor(cnt, 0), fwht_xor(f, 0);
    for(int i = 0 ; i < len ; i ++) cnt[i] *= f[i];
    fwht_xor(cnt, 1);

    cout << *min_element(cnt.begin(), cnt.end()) << endl;;

    return 0;
}

C++(clang++ 11.0.1) 解法, 执行用时: 93ms, 内存消耗: 40036K, 提交时间: 2022-08-06 09:51:05

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
const int N = 2500005 ;
int n,m,val[N] ;
ll A[N],B[N] ;
char S[N] ;
void polyXOR(ll *a,int n,bool flag=1)
{
	for(int mid=2,k=1;mid<=n;mid<<=1,k<<=1)
		for(int i=0;i<n;i+=mid)
			for(int j=0;j<k;j++)
			{
				ll x=a[i+j],y=a[i+j+k] ;
				a[i+j]=(x+y) ;
				a[i+j+k]=(x-y) ;
				if(!flag)
				{
					a[i+j]>>=1 ;
					a[i+j+k]>>=1 ;
				}
			}
}
int get(int x)
{
	int ans=0 ;
	while(x) ans+=x&1,x>>=1 ;
	return ans ;
}
int main()
{
	scanf("%d%d",&n,&m) ;
	for(int i=1;i<=n;++i)
	{
		scanf("%s",S+1) ;
		for(int j=1;j<=m;j++)
			val[j]=val[j]*2+S[j]-'0' ;
	}
	memset(A,0,sizeof(A)) ;
	memset(B,0,sizeof(B)) ;
	for(int i=1;i<=m;++i) A[val[i]]++ ;
	for(int i=0;i<(1<<n);++i) B[i]=min(get(i),n-get(i)) ;
	n=(1<<n) ;
    polyXOR(A,n) ; polyXOR(B,n) ;
	for(int i=0;i<n;++i) A[i]=A[i]*B[i] ;
	polyXOR(A,n,0) ;
	ll ans=1e18 ;
	for(int i=0;i<n;++i) ans=min(ans,A[i]) ;
	printf("%lld\n",ans) ;
	return 0 ;
}