题面
http://codeforces.com/contest/662/problem/C
题解
前置知识
看到n仅仅20，自然想到状压。
因为每一行、列最多操作一次即可，所以注意到一个性质：如果每一行分别有没有操作已经确定，答案就确定了；因为每一列是否操作是互相独立的，如果操作能使答案变小就操作，否则就不操作。
形式化地说，设num[x]表示x的二进制表示中1的个数，并定义
[b[x] = min (num[x],num[2^n-x-1])
]
然后，每一行是否操作状压成一个数mask，初始时每一列的状态压成situ[1]~situ[m]，那么对于固定的mask，答案是(sum_{i=1}^{m}b[mask igoplus situ[i]])，下记这个东西为c[mask]。由于有异或，所以我们尽量往异或卷积上凑：
[{sumlimits_{i=1}^{m}b[mask igoplus situ[i]]}
]
[=sumlimits_{x=0}^{2^n-1}(sumlimits_{i=1}^{m}[situ[i]=x])b[mask igoplus x]
]
[={sumlimits_{x=0}^{2^n-1}}(sumlimits_{i=1}^{m}[situ[i]=x])sumlimits_{y=0}^{2^n-1}[xigoplus y=mask]b[y]
]
好了，如果设(a[x]=sum_{i=1}^{m}[situ[i]=x])，式子就化简成了
[c[mask]=sumlimits_{xigoplus y=mask}a[x]b[y]
]
FWT结束此题。
总时间复杂度(O(2^nn))。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define rg register
#define In inline
const ll N = 1048576;
const ll M = 100000;
In ll read(){
ll s = 0,ww = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){if(ch == '-')ww = -1;ch = getchar();}
while('0' <= ch && ch <= '9'){s = 10 * s + ch - '0';ch = getchar();}
return s * ww;
}
In void calc(ll &x,ll &y,ll opt){
if(opt == 1){
ll X = x + y,Y = x - y;
x = X,y = Y;
}
else{
ll X = (x + y) >> 1,Y = (x - y) >> 1;
x = X,y = Y;
}
}
void FWT(ll a[],ll deg,ll opt){
for(rg int n = 2;n <= deg;n <<= 1){
int m = n >> 1;
for(rg int i = 0;i < deg;i += n)
for(rg int j = 0;j < m;j++)
calc(a[i+j],a[i+j+m],opt);
}
}
ll n,m,deg;
ll a[N+5],b[N+5],c[N+5],num[N+5];
ll situ[M+5];
char s[M+5];
int main(){
n = read();m = read(),deg = 1ll << n;
for(rg int i = 1;i <= n;i++){
scanf("%s",s + 1);
for(rg int j = 1;j <= m;j++)situ[j] = ((situ[j]<<1) | (s[j]-'0'));
}
for(rg int i = 1;i <= m;i++)a[situ[i]]++;
for(rg int i = 1;i < deg;i++)num[i] = num[i>>1] + (i&1);
for(rg int i = 0;i < deg;i++)b[i] = min(num[i],num[deg-i-1]);
FWT(a,deg,1);
FWT(b,deg,1);
for(rg int i = 0;i < deg;i++)c[i] = a[i] * b[i];
FWT(c,deg,-1);
ll ans = n * m;
for(rg int i = 0;i < deg;i++)ans = min(ans,c[i]);
cout << ans << endl;
return 0;
}