听说这是一道$ Tourist$现场没出的题
题意：
给定$n*m的 01$矩阵，可以任意反转一行/列($0$变$1$，$1$变$0$)，求最少$ 1$的数量
$ n<=20 \ m<=100000$
$ Solution$
考虑暴力
枚举每一行反转/不反转
预处理$ g(s)$表示某状态为$ s$的列的最少$ 1$的数量
显然$ g(s)=min(popcount(s),n-popcount(s))$
枚举每行是否反转之后直接$ O(m)$计算即可
时间复杂度$ O(2^n m)$，无法通过这题
容易发现瓶颈在于暴力枚举行状态之后无法快速计算答案
我们令$ f(s)$表示列状态为$ s$的列的出现次数，$ F(s)$表示行反转状态为$ s$的时候的答案
转移有$ F(s)=\sum\limits_{i=0}^{2^n-1}f(i)g(i \ xor \ s)$
由于$ i \ xor \ i \ xor \ s = s$
所以可以化简为$ F(s)=\sum\limits_{i \ xor \ j =s}f(i)g(j)$
是一个$ FWT$卷积的形式
直接$ FWT$优化
时间复杂度：$ O(nm+2^n n)$
注意$ FWT$过程中可能要开$ long \ long$
$ my \ code:$
#include<ctime>
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
#define rt register int
#define ll long long
using namespace std;
inline ll read(){
ll x = ; char zf = ; char ch = getchar();
while (ch != '-' && !isdigit(ch)) ch = getchar();
if (ch == '-') zf = -, ch = getchar();
while (isdigit(ch)) x = x * + ch - '', ch = getchar(); return x * zf;
}
void write(ll y){if(y<)putchar('-'),y=-y;if(y>)write(y/);putchar(y%+);}
void writeln(const ll y){write(y);putchar('\n');}
int i,j,k,m,n,x,y,z,cnt,invn;
void fwt(int n,ll *a,int fla){
for(rt i=;i<n;i<<=)
for(rt j=;j<n;j+=i<<)
for(rt k=;k<i;k++){
ll x=a[j+k],y=a[i+j+k];
a[j+k]=x+y;a[i+j+k]=x-y;
}
if(fla==-)for(rt i=;i<n;i++)a[i]/=n;
}
char c[][];
int s[];ll f[],g[];
#define cnt(x) __builtin_popcount(x)
int main(){
n=read();m=read();
for(rt i=;i<=n;i++)scanf("%s",c[i]+);
for(rt i=;i<=n;i++)
for(rt j=;j<=m;j++)s[j]=s[j]<<|(c[i][j]=='');
for(rt i=;i<=m;i++)g[s[i]]++;
for(rt i=;i<(<<n);i++)f[i]=min(cnt(i),n-cnt(i));
fwt(<<n,f,);fwt(<<n,g,);
for(rt i=;i<<<n;i++)f[i]=f[i]*g[i];
fwt(<<n,f,-);
cout<<*min_element(f,f+(<<n));
return ;
}