Chlience

【题解】Codeforces 662 C Binary Table
Problem给定 $n$ 行 $m$ 列的 $01$ 矩阵,每次可以翻转一行或者一列,最少有多少个 $1$Tho...
扫描右侧二维码阅读全文
04
2019/03

【题解】Codeforces 662 C Binary Table

Problem

给定 $n$ 行 $m$ 列的 $01$ 矩阵,每次可以翻转一行或者一列,最少有多少个 $1$

Thought

naive 做法

观察到 $n$ 较小,并且横纵翻转相互影响,那么考虑枚举横行的翻转情况

在横行确定之后,纵列每一列是否翻转就可以 $O(n)$ 的计算出来,或者用一个 $bitset$ 将当前纵列的情况压起来,异或上横行的翻转情况,即为当前情况

通过计算有多少个 $1$ 即可算出当前纵列是否需要翻转,提前预处理出每个二进制数有多少个 $1$ ,即可实现 $O(1)$ 计算每列翻转情况

并且发现,如果横行的两个翻转互补,那么其意义相同,所以可以少枚举一次

总时间复杂度 $O(\frac{2^nm}{2})$

professional 做法

考虑到枚举每个横行翻转情况之后,需要计算每个纵列的答案

设 $S$ 为横行翻转情况,$f(S)$ 为该情况下的答案,全集为 $U$,那么有

$$ f(S)=\sum_{T}num[T]*\min \{count(S\oplus T),count(S\oplus T\oplus U)\} $$

考虑枚举 $X=S\oplus T$

$$ f(S)=\sum_{X}num[X\oplus S]*\min \{count(X),count(X\oplus U)\} $$

令 $G(X)=\min \{count(X),count(X\oplus U)\}$

$$ f(S)=\sum_{X}num[X\oplus S]*G(X) $$

这就化为了异或卷积的形式,使用 $FWT$ 即可

Code

#include <bits/stdc++.h>
using namespace std;
int read() {
    int ans = 0, flag = 1;
    char ch = getchar();
    while(ch > '9' || ch < '0') {if(ch == '-') flag = - flag; ch = getchar();}
    while(ch >= '0' && ch <= '9') {ans = ans * 10 + ch - '0'; ch = getchar();}
    return ans * flag;
}
const int N = 1 << 20;
const int mod = 1000000007;
const int inv2 = 500000004;
int n, m, U;
char str[21][100010];
int g[N], f[N];
int num[N];

int lowbit(int x) {return x & (- x);}
void FWT(int *a, int n, int f) {
    for(int i = 1; i < n; i <<= 1)
        for(int j = 0; j < n; j += (i << 1))
            for(int k = 0; k < i; ++ k) {
                int x = a[j + k], y = a[i + j + k];
                a[j + k] = 1ll * (x + y) % mod;
                a[i + j + k] = 1ll * (x - y + mod) % mod;
                if(f == - 1) {
                    a[j + k] = 1ll * a[j + k] * inv2 % mod;
                    a[i + j + k] = 1ll * a[i + j + k] * inv2 % mod;
                }
            }
}
int main() {
    n = read(); m = read();
    U = (1 << n) - 1;
    for(int i = 1; i < (1 << n); ++ i)
        num[i] = num[i - lowbit(i)] + 1;
    for(int i = 0; i < (1 << n); ++ i)
        g[i] = min(num[i], num[i ^ U]);
    for(int i = 0; i < n; ++ i)
        scanf("%s", str[i]);
    for(int i = 0; i < m; ++ i) {
        int now = 0;
        for(int j = 0; j < n; ++ j)
            if(str[j][i] == '1')
                now |= (1 << j);
        ++ f[now];
    }
    FWT(f, 1 << n, 1); FWT(g, 1 << n, 1);
    for(int i = 0; i < (1 << n); ++ i)
        f[i] = 1ll * f[i] * g[i] % mod;
    FWT(f, 1 << n, - 1);
    int ans = n * m;
    for(int i = 0; i < (1 << n); ++ i)
        ans = min(ans, f[i]);
    printf("%d\n", ans);
    return 0;
}
Last modification:March 4th, 2019 at 04:42 pm

Leave a Comment