CF662C Binary Table

题目链接

题意

给出一个 $n\times m$ 的 $0,1$ 矩阵,可以选择一些行或列进行取反,矩阵中 $1$ 的个数最少可以是多少
$1\leq n\leq 20, 1\leq m\leq 100000$

题解

比较妙,我没想出来
发现 $2^n$ 枚举 $n$ 行的取反状态是可行的,但是这样之后应该怎么样快速计算贡献
考虑将每一列 $n$ 个 $0,1$ 由二进制转化为一个十进制数,然后将所有列按照这个数来分类考虑,称这个数为代表数
假设现在 $n$ 行的取反状态为 $S$ ,我们想求出此时的最小的 $1$ 的个数
设对于某个代表数 $i$ ,求出了在 $m$ 列中代表数为 $i$ 的列数有 $g_i$ 个
对于这个代表数 $i$ ,可以求出取反或不取反使得其中包含 $1$ 最少的个数 $f_i$

此时有转移
$$ans_S=\sum_{i=0}^{2^n-1} g_i\cdot f_{i\oplus S} $$

$$ans_S=\sum_{i\oplus j=S} g_i\cdot f_j$$
其中 $\oplus$ 表示异或
所以快速求出 $f,g$ 后做一个异或卷积就可以得到最后的 $ans$ 数组,从中选择一个最小的就是答案了

程序

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>

#define reg register
#define MAX_N 2000007
#define MAX_M 100007
typedef long long ll;

int N, M;
int mp[27][MAX_M];
ll f[MAX_N], g[MAX_N];
char s[MAX_M];

inline void FWT (ll *A, int M, ll type) {
    for (int l = 1; l < M; l <<= 1) {
        for (int i = 0, L = l << 1; i < M; i += L) {
            for (int j = 0; j < l; ++j) {
                ll x = A[i + j], y = A[i + j + l];
                A[i + j] = x + y, A[i + j + l] = x - y;
                if (type == -1)
                    A[i + j] /= 2LL, A[i + j + l] /= 2LL;
            }
        }
    }
}

int main () {
    read(N), read(M);
    for (int i = 1; i <= N; ++i) {
        scanf("%s", s + 1);
        for (int j = 1; j <= M; ++j)
            mp[i][j] = s[j] - '0';
    }
    for (int i = 1; i <= M; ++i) {
        int s = 0;
        for (int j = 1; j <= N; ++j)
            s += mp[j][i] * (1 << j - 1);
        g[s]++;
    }
    ll res = N * M + 1;
    M = 1 << N;
    for (int i = 0; i < M; ++i) {
        int s = i, c1 = 0;
        while (s)
            c1 += (s & 1), s >>= 1;
        f[i] = std::min(c1, N - c1);
    }
    FWT(f, M, 1), FWT(g, M, 1);
    for (int i = 0; i < M; ++i)
        f[i] *= g[i];
    FWT(f, M, -1);
    for (int i = 0; i < M; ++i)
        res = std::min(res, f[i]);
    printf("%lld\n", res);
    return 0;
}

sys_con

高一 OIer,常规 / 竞赛都渣得不行

发表评论

电子邮件地址不会被公开。 必填项已用*标注