有一个$n\times m$的表格$(n\leq20,m\leq10^5)$

每个表格里面有一个$0/1$，
每次可以将一行或者一列的$01$全部翻转。

回答表格中最少有多少个$1$

对每列进行处理即为二进制数。

表格的翻转可以用$\oplus$表示。
设$f(x)$=$x$这个状态的列有几个，$g(x)$为每个状态最少有多少个$0$。

枚举如何翻转$m$

$c_m=\sum f(i)g(i\oplus m)$

$FWT$即可。

代码

```c++

include

using namespace std;
typedef long long ll;

define pii pair

define mk make_pair

const int N = 1 << 20;
const int M = 1e5 + 10;
const int mod = 1e9 + 7;
int read()
{
int x = 0, f = 1;
char c = getchar();
while (c < ‘0’ || c > ‘9’)
{
if (c == ‘-‘)
f = -1;
c = getchar();
}
while (c >= ‘0’ && c <= ‘9’)
x = (x << 1) + (x << 3) + c - ‘0’, c = getchar();
return x f;
}
int qpow(int a, int x, int mo)
{
int res = 1;
while (x)
{
if (x & 1)
res = 1ll res a % mo;
x >>= 1;
a = 1ll a a % mo;
}
return res;
}
int inc(int x, int y, int mo)
{
if (y < 0)
y += mo;
if (x + y >= mo)
x -= mo;
return x + y;
}
int Inv2;
void FWT(int A, int n, int op, int t) //t=1 or t=2 and t=3 xor
{
for (int i = 2; i <= n; i <<= 1)
{
for (int j = 0, mid = i >> 1; j < n; j += i)
for (int k = 0; k < mid; k++)
{

            if (t == 1)
                A[j + mid + k] = inc(A[j + mid + k], A[j + k] * op, mod);
            else if (t == 2)
                A[j + k] = inc(A[j + k], A[j + mid + k] * op, mod);
            else if (t == 3)
            {
                int x = A[j + k], y = A[j + mid + k];
                if (op == 1)
                    A[j + k] = (x + y) % mod, A[j + mid + k] = (x - y + mod) % mod;
                else
                    A[j + k] = 1ll * Inv2 * (x + y) % mod, A[j + mid + k] = 1ll * Inv2 * (x - y + mod) % mod;
            }
        }
}

}
void FWTX(int A, int B, int n, int t)
{
Inv2 = qpow(2, mod - 2, mod);
FWT(A, n, 1, t), FWT(B, n, 1, t);

for (int i = 0; i < n; ++i)
    A[i] = 1ll * A[i] * B[i] % mod;
FWT(A, n, -1, t);

}
int f[N], g[N];
char s[20][M];
int main()
{
int n = read(), m = read();
for (int i = 0; i < (1 << n); i++)
g[i] = min(n - builtin_popcount(i), builtin_popcount(i));
for (int i = 0; i < n; i++)
scanf(“%s”, s[i]);
for (int i = 0; i < m; i++)
{
int st = 0;
for (int j = 0; j < n; j++)
if (s[j][i] == ‘1’)
st |= 1 << j;
f[st]++;
//cout << st << endl;
}
FWTX(f, g, (1 << n), 3);
int res = 1e9;
for (int i = 0; i < (1 << n); i++)
res = min(res, f[i]);
printf(“%d\n”, res);
}