题解 CF662C 【Binary Table】

简单的$FWT$模板题。 这道题有一个简单的做法，就是考虑枚举列状态，然后$O(m)$计算。 这样是$O(2^nm)$的，显然过不去。考虑使用优化。 设$dp[i]=min\{bit[i],bit[i\otimes (2^n-1)]\}$，其中$bit[i]$表示$i$的二进制位有多少个$1$。设$f[i]$表示所有的行中出现$i$的次数。设$ans[i]$表示列翻转状态为$i$的答案最小值。 $\because i\otimes (i\otimes j)=j$ 所以存在转移: $\displaystyle ans[i]=\sum_{j\otimes k=i}f[j]*dp[k]$ 利用$FWT$优化转移即可。时间复杂度$O(2^nn)$。 代码: ```cpp #include<bits/stdc++.h> #include<ext/pb_ds/assoc_container.hpp> #define Rep(i,a,b) for(register int i=(a),i##end=(b);i<=i##end;++i) #define Repe(i,a,b) for(register int i=(a),i##end=(b);i>=i##end;--i) #define For(i,a,b) for(i=(a),i<=(b);++i) #define Forward(i,a,b) for(i=(a),i>=(b);--i) #define Chkmin(a,b) a=a<b?a:b #define Chkmax(a,b) a=a>b?a:b #define pb push_back template<typename T>inline void read(T &x) { T f=1;x=0;char c; for(c=getchar();!isdigit(c);c=getchar())if(c=='-')f=-1; for(;isdigit(c);c=getchar())x=x*10+(c^48); x*=f; } using namespace std; void file() { #ifndef ONLINE_JUDGE freopen("water.in","r",stdin); freopen("water.out","w",stdout); #endif } const int MAXN=1e5+7; static int n,m; static int a[MAXN]; inline void get(char &x){for(x=getchar();!isdigit(x);x=getchar());} static long long cnt[1<<20],dp[1<<20]; static int bit[1<<20],maxx; inline void init() { read(n);read(m);maxx=(1<<n)-1; static char x; Rep(i,1,n)Rep(j,1,m)get(x),a[j]<<=1,a[j]+=x^48; Rep(i,1,m)++cnt[a[i]]; Rep(i,1,maxx)bit[i]=bit[i>>1]+(i&1); Rep(i,1,maxx)dp[i]=min(bit[i],bit[i^maxx]); } inline void FWT(long long *a,int Len) { static long long t; for(register int i=2,ii=1;i<=Len;i<<=1,ii<<=1) for(register int j=0;j<Len;j+=i) Rep(k,0,ii-1) { t=a[j+k]; a[j+k]+=a[j+k+ii]; a[j+k+ii]=t-a[j+k+ii]; } } inline void IFWT(long long *a,int Len) { static long long t; for(register int i=2,ii=1;i<=Len;i<<=1,ii<<=1) for(register int j=0;j<Len;j+=i) Rep(k,0,ii-1) { t=a[j+k]; a[j+k]+=a[j+k+ii]; a[j+k+ii]=t-a[j+k+ii]; a[j+k]>>=1;a[j+k+ii]>>=1; } } static int ans; inline void solve() { FWT(dp,maxx+1);FWT(cnt,maxx+1); Rep(i,0,maxx)dp[i]*=cnt[i]; IFWT(dp,maxx+1); ans=n*m; Rep(i,0,maxx)Chkmin(ans,dp[i]); printf("%d\n",ans); } int main() { file(); init(); solve(); //cerr<<1.0*clock()/CLOCKS_PER_SEC<<endl; return 0; } ```