正題
題目連結:https://www.luogu.com.cn/problem/CF662C
題目大意
\(n*m\)的網格上有\(0/1\)，可以任意翻轉行和列，求剩下最少的\(1\)。
解題思路
知道是\(FWT\)之後就好做很多了。
首先因為\(n\)很小，是以可以考慮枚舉翻轉的行數，我們現在需要對于一個行的翻轉狀态快速知道最小值。
如果一行狀态\(s\)翻轉行狀态\(w\)之後就相當于\(val(s\ xor\ w)\)反過來也就是若\(c=s\ xor\ w\)那麼\(s\ xor\ c=w\)。
此時就可以上\(FWT\)了，設\(val_i\)表示列狀态\(i\)的最小值，\(num_i\)表示列狀态\(i\)的數量。那麼$$ans(s)=\sum_{i\ xor\ j=s}val_i\times num_j$$
上\(FWT\)即可，時間複雜度\(O(2^nn+nm)\)
\(code\)
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=(1<<21);
ll n,m,val[N],num[N],ans;
char s[20][110000];
void FWT(ll *f,ll op){
for(ll p=2;p<=n;p<<=1)
for(ll k=0,len=p>>1;k<n;k+=p)
for(ll i=k;i<k+len;i++){
ll x=f[i],y=f[i+len];
f[i]=(x+y)/op;
f[i+len]=(x-y)/op;
}
return;
}
void solve(ll *a,ll *b){
FWT(a,1);FWT(b,1);
for(ll i=0;i<n;i++)
a[i]=a[i]*b[i];
FWT(a,2);return;
}
int main()
{
scanf("%lld%lld",&n,&m);
for(ll i=0;i<n;i++)
scanf("%s",s[i]);
ll MS=(1<<n);
for(ll i=1;i<MS;i++)
val[i]=val[i-(i&-i)]+1;
for(ll i=0;i<MS;i++)
val[i]=min(val[i],n-val[i]);
for(ll i=0;i<m;i++){
ll w=0;
for(ll j=0;j<n;j++)
w+=(s[j][i]=='1')<<j;
num[w]++;
}
n=MS;solve(val,num);ans=1e9;
for(ll i=0;i<n;i++)
ans=min(ans,val[i]);
printf("%lld\n",ans);
}