CF662C Binary Table

注意到 $n$ 很小，$m$ 很大，考虑对 $n$ 状压，记 $f _ s$ 为状态为 $s$ 的列有多少个。对于一个状态，即一列内的翻转将 $0$ 换成 $1$ ，将 $1$ 换成 $0$ ，相当于对一个状态取其中的最小值，记 $g _ s$ 为一个状态的最小值。

现在考虑行的变换，同样可以用一个状态 $t$ 表示哪些行要变换，那么对于每一列的该行都要变化，状态 $s$ 变为 $s \oplus t$ 。则答案可以表示为：
$$
\sum _ s f _ s g _ {s \oplus t}
$$
记 $s \oplus t = k$ ，则
$$
\sum _ s f _ s \sum _ k g _ k [s \oplus t = k]
$$
因为 $s \oplus t = k \Longleftrightarrow s \oplus k = t$ ，对于 $t$ ，故答案为：
$$
\sum _ s f _ s \sum _ k g _ k [s \oplus k = t]
$$
做异或卷积，可以获得所有 $t$ 的答案，取最小值即可。

查看代码

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long LL;
template <class Type>
void read(Type &x)
{
    char c;
    bool flag = false;
    while ((c = getchar()) < '0' || c > '9')
        c == '-' && (flag = true);
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
    flag && (x = ~x + 1);
}
template <class Type>
void write(Type x)
{
    x < 0 && (putchar('-'), x = ~x + 1);
    x > 9 && (write(x / 10), 0);
    putchar(x % 10 + '0');
}
const int N = 20, M = 1e5 + 10;
char str[N][M];
int cnt[1 << N];
LL f[1 << N], g[1 << N];
void fwt(LL *x, int bit, int op)
{
    int tot = 1 << bit;
    for (int mid = 1; mid < tot; mid <<= 1)
        for (int i = 0; i < tot; i += mid << 1)
            for (int j = 0; j < mid; j++)
            {
                LL p = x[i | j], q = x[i | j | mid];
                x[i | j] = (p + q) / op, x[i | j | mid] = (p - q) / op;
            }
}
int main()
{
    int n, m;
    read(n), read(m);
    for (int i = 0; i < n; i++)
        scanf("%s", str[i]);
    for (int j = 0; j < m; j++)
    {
        int x = 0;
        for (int i = 0; i < n; i++)
            x = x << 1 | str[i][j] - '0';
        f[x]++;
    }
    for (int i = 0; i < 1 << n; i++)
    {
        cnt[i] = cnt[i >> 1] + (i & 1);
        g[i] = min(cnt[i], n - cnt[i]);
    }
    fwt(g, n, 1), fwt(f, n, 1);
    for (int i = 0; i < 1 << n; i++)
        f[i] *= g[i];
    fwt(f, n, 2);
    int res = n * m;
    for (int i = 0; i < 1 << n; i++)
        res = min(res, (int)f[i]);
    write(res);
    return 0;
}