题目链接：Codeforces 662 C

你有一个 $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;
}
最后修改：2020 年 12 月 22 日
© 允许规范转载
如果觉得我的文章对你有用，请随意赞赏