题解：AT_abc396_g [ABC396G] Flip Row or Col

· · 题解

提供一个 FWT 做法。

首先，我们看到输入的 W 十分小，于是考虑 2^W 枚举每一列是否翻转的状态，记为 s。对于第 i 行，将这一行的数改为用二进制表示，记为 B_i。

我们设 \text{popcount(x)} 表示 x 在二进制下 1 的个数，\oplus 表示异或运算，那么说如果 W-\text{popcount}(B_i\oplus s)<\text{popcount}(B_i\oplus s)，就说明这一行全部异或一产生的贡献会更小，于是选择异或一。

设 f(s) 表示当每一列是否翻转的状态为 s 时矩阵中一的个数最少是多少，那么容易得出:

f(s)=\sum_{i=1}^H\min(\text{popcount}(B_i\oplus s),W-\text{popcount}(B_i\oplus s))\\ ans=\min_{s=0}^{2^W-1}f(s)

现在我们考虑如何快速求出所有 f(s)。

设 h(s)=\min(\text{popcount}(s),W-\text{popcount}(s))，g(s)=\sum_{i=1}^{H}[B_i=s]。

于是我们考虑化繁一下式子：

\begin{aligned} f(s)=&\sum_{i=1}^Hh(B_i\oplus s)\\ =&\sum_{i=1}^H\sum_{y=0}^{2^W-1}[B_i\oplus s=y]h(y)\\ =&\sum_{y=0}^{2^W-1}h(y)\sum_{i=1}^H[B_i\oplus y=s]\\ =&\sum_{y\oplus z=s}h(y)g(z) \end{aligned}

然后就可以用 FWT 快速求解了。

code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<18)+10;
int m,n;
ll A[N],B[N];
ll a[N],b[N];
void xorr(ll*f,double type)
{
    for(int len=2;len<=n;len<<=1)
    {
        int mid=len>>1;
        for(int i=0;i<n;i+=len)
        {
            for(int j=0;j<mid;j++)
            {
                f[i+j]+=f[i+j+mid];
                f[i+j+mid]=f[i+j]-2*f[i+j+mid];
                f[i+j]=f[i+j]*type,f[i+j+mid]=f[i+j+mid]*type;
            }
        }
    }
}
int we;
string s;
#define popcount(x) __builtin_popcount(x)
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>we>>m,n=1<<m;
    for(int i=1;i<=we;i++){
        cin>>s;
        int sum=0;
        for(int i=0;i<m;i++) sum=sum+((s[i]-'0')<<i);
        a[sum]++;
    }
    for(int i=0;i<n;i++) b[i]=min(popcount(i),popcount(n-1-i));
    xorr(a,1),xorr(b,1);
    for(int i=0;i<n;i++) a[i]=a[i]*b[i];
    xorr(a,0.5);
    ll ans=1e18;
    for(int i=0;i<n;i++) ans=min(ans,a[i]); 
    cout<<ans<<"\n";
    return 0;
}