【CF662C】Binary Table

题目

好吧，我连板子都不会了

有一个非常显然的做法就是\(O(2^nm)\)做法就是枚举每一行的状态，之后我们贪心去看看每一列是否需要翻转就好啦

显然这个做法非常垃圾过不去

首先我们发现每一列都不超过\(20\)，考虑把每一列都压成一个状态

我们考虑设一些奇怪的东西

设\(g_i\)表示行的翻转状态为\(i\)的最优解，\(f_i\)表示有多少列的状态为\(i\)，\(dp_i\)表示\(i\)这个状态最少有多少个\(1\)

显然\(dp_i=min\{bit(i),n-bit(i)\}\)

我们考虑有一列原来的状态是\(k\)，行的翻转状态为\(i\)，翻转之后这一列的状态是\(j\)

就会存在\(i\bigoplus k=j\)，也就是\(i=j\bigoplus k\)

也就是说

\[g_i=\sum_{j\bigoplus k=i}f_k\times dp_j
\]

发现这是一个异或卷积，于是我们\(fwt\)一下就好了

代码

#include<algorithm>

#include<iostream>

#include<cstring>

#include<cstdio>

#define re register

#define LL long long

#define max(a,b) ((a)>(b)?(a):(b))

#define min(a,b) ((a)<(b)?(a):(b))

const int maxn=(1<<20)+6;

LL cnt[maxn],dp[maxn],f[maxn];

int n,m,len;

char S[21][100005];

inline int Fwt(LL *t,int o) {

    for(re int i=2;i<=len;i<<=1)

        for(re int ln=i>>1,l=0;l<len;l+=i)

            for(re int x=l;x<l+ln;++x) {

                LL g=t[x],h=t[x+ln];

                t[x]=g+h,t[ln+x]=g-h;

                if(o) t[x]/=2ll,t[x+ln]/=2ll;

            }

}

int main() {

    scanf("%d%d",&n,&m);len=(1<<n);

    for(re int i=0;i<len;i++) cnt[i]=cnt[i>>1]+(i&1);

    for(re int i=0;i<len;i++) dp[i]=min(cnt[i],cnt[(len-1)^i]);

    for(re int i=1;i<=n;i++) scanf("%s",S[i]+1);

    for(re int i=1;i<=m;i++) {

        int now=0;

        for(re int j=1;j<=n;j++) {

            if(S[j][i]=='1') now|=1;

            now<<=1;

        }

        f[now>>1]++;

    }

    Fwt(f,0),Fwt(dp,0);

    for(re int i=0;i<len;i++) f[i]*=dp[i];

    Fwt(f,1);LL ans=f[0];

    for(re int i=1;i<len;i++) ans=min(ans,f[i]);

    std::cout<<ans;

    return 0;

}