题解：AT_abc396_g [ABC396G] Flip Row or Col

elswzl · 2025-03-19 23:48:22 · 题解

思路

我们先转换一下题意：给你一个数组 a 包含 n 个长度为 m 的二进制数，让你找出一个二进制数 s 满足 \sum{\min(\operatorname{popcount}(a_i\operatorname{xor} s),m-\operatorname{popcount}(a_i\operatorname{xor} s))} 的值最小，并且输出那个值。

我们定义 f_{s,i} 表示对于二进制数 s 和数字 i 来说，a 中有多少个数字和 s 的汉明距离恰好为 i。

最后转移的式子如下：

当然这个式子还是太抽象了，大概说一下含义。

假设每个二进制数都是一个点，然后与之汉明距离为 1 的点连一条边，再设置该点权值为 a 中出现多少次该点，那么 f_{s,i} 就是距离 s 为 i 的点的权值之和。

我们先加上 \sum{f_{t,i-1}} 的值，发现算重了走过 s 的路径，所以减去 m\times\sum{f_{s,i-2}}，后面以此类推。

然而算完之后却发现多算了好多。这是因为对于每条路径，都有 i 种开始的方法，也就是乘上 \frac{1}{i} 就可以了。

最终复杂度 O(2^M\times M^3)，当然显然可以优化掉一个 M，但没必要。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=18,inf=1e18;
int n,m,f[(1<<N)+2][N+2];
int ans;
signed main(){
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
    ans=inf;
    for(int i=1;i<=n;i++){
        int x=0;
        for(int j=1;j<=m;j++){
            char y;cin>>y;
            x=(x<<1)|(y-'0');
        }
        f[x][0]++;
    }
    for(int i=1;i<=m;i++){
        for(int s=0;s<1<<m;s++){
            for(int j=1;j<=m;j++){
                int t=s^(1<<j-1);
                for(int k=i-1;k>=0;k--){
                    if((i^k)&1)f[s][i]+=f[t][k];
                    else f[s][i]-=f[s][k];
                }
            }
            f[s][i]/=i;
        }
    }
    for(int s=0;s<1<<m;s++){
        int num=0;
        for(int i=0;i<=m;i++)num+=min(i,m-i)*f[s][i];
        ans=min(ans,num);
    }
    cout<<ans<<"\n";
    return 0;
}

顺带，这题评紫真的合适吗……