[Easy-Medium] AT_abc396_g [ABC396G] Flip Row or Col

简要题意

给定一个 $n\times m$ 的 $01$ 矩阵 $A$，你可以进行任意次操作，每次操作选定一行或一列，将每一个单元格的数字取反，你需要最小化所有数的和，输出这个最小值。

$1\leq n\leq 2\times 10^5,1\leq m\leq 18$。

思路

首先注意到 $O(2^m)$ 是可以接受的，于是可以考虑枚举每一列是否操作，然后快速判断一行是否操作（操作显然可交换）。

根据这个思路，可以发现我们需要求的就是下面这个式子：

$$\min_{S=1}^{2^m-1} \sum_{i=1}^{n}\min(|a_i\oplus S|,m-|a_i\oplus S|)$$

其中 $a_i$ 表示 $A$ 的第 $i$ 行的 bitmask。

于是只需要快速计算上述式子即可。注意到我们要求和的东西是一个关于 $a_i\oplus S$ 的函数，不妨记 $f(x)=\min(|x|,m-|x|)$，则将式子改写为：

$$\min_{S=1}^{2^m-1} \sum_{i=1}^{n} f(a_i\oplus S)$$

由于 $\min$ 结构和异或在本题中似乎不太相容，于是我们只需要对于每一个 $S$ 求出和式的值，然后取最小值即可。我们直接考察和式：

$$\sum_{i=1}^{n} f(a_i\oplus S)$$

尝试改为枚举 $a_i\oplus S$：

$$\sum_{T=1}^{2^m-1} f(T)c_{S\oplus T}$$

其中 $c_i=\sum_{j}[a_j=i]$ 即 $i$ 在 $a$ 中的出现次数。

将和式进一步改写得：

$$\sum_{X\oplus Y=S}f(X)c_Y$$

这是 XOR 卷积的形式，直接用 FWT 解决即可。时间复杂度 $O(n+m2^m)$。

代码

#include <bits/stdc++.h>
using namespace std;

constexpr int mod = 998244353, inv2 = (mod + 1) >> 1;
int Add(int x, int y){ return (x + y) >= mod ? (x + y - mod) : (x + y); }
int Sub(int x, int y){ return (x - y) < 0 ? (x - y + mod) : (x - y); }
int Mul(int x, int y){ return 1ll * x * y % mod; }

const int N = 2e5 + 5, M_ = (1 << 18) + 5;
int n, m, a[N], f[M_], c[M_];

void fwt(int *a, int n, int tag){
    for(int x=2;x<=n;x<<=1){
        int k = x >> 1;
        for(int i=0;i<n;i+=x){
            for(int j=0;j<k;j++){
                a[i + j] = Add(a[i + j], a[i + j + k]);
                a[i + j + k] = Sub(a[i + j], Add(a[i + j + k], a[i + j + k]));
                a[i + j] = Mul(tag, a[i + j]);
                a[i + j + k] = Mul(tag, a[i + j + k]);
            }
        }
    }
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for(int i=1;i<=n;i++){
        string x; cin >> x;
        for(int j=1;j<=m;j++) a[i] |= ((x[j - 1] - '0') << (j - 1));
        c[a[i]]++;
    }
    for(int i=0;i<(1<<m);i++) f[i] = min(__builtin_popcount(i), m - __builtin_popcount(i));
    fwt(c, 1 << m, 1), fwt(f, 1 << m, 1);
    for(int i=0;i<(1<<m);i++) f[i] = Mul(f[i], c[i]);
    fwt(f, 1 << m, inv2);
    cout << *min_element(f, f + (1 << m)) << '\n';
    return 0;
}

// Written by xiezheyuan

Submission。