CF662C Binary Table（FWT）

[Luogu-CF662C]

FWT_xor

題目描述

有一個 \(n\) 行 \(m\) 列的表格，每個元素都是 $0/1 $，每次操作可以選擇一行或一列，把 \(0/1\) 翻轉，即把 \(0\) 換為 \(1\) ，把 \(1\) 換為 \(0\) 。請問經過若干次操作后，表格中最少有多少個 \(1\) 。

首先可以想到\(O(2^N*M)\)的暴力,即枚舉每一行是否翻轉,然后\(O(M)\)計算

設\(f_k\)表示選擇了狀態為\(k\)的那些行，\(a_i\)表示有多少列的二進制表示等于\(i\)，\(b_j\)表示\(j\)中\(0\)個數和\(1\)個數的較小值，

我們有\(f_k=∑_{i?k=j}{a_i}{b_j}\)，這相當于枚舉對哪些行進行操作（\(k\)），然后對于二進制表示為\(i\)的列（有\(a_i\)列，做完行變換后這一列的值為\(i?k\)），貪心（\(b_j\)）地選擇是否對這一列做變換，用異或的性質把\(j,k\)互換，我們得到\(f_k=∑_{i?j=k}{a_i}{b_j}\)，這是一個卷積的形式，可以用FWT快速求得答案

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define Debug(x) cout<<#x<<"="<<x<<endl
using namespace std;
typedef long long LL;
const int INF=1e9+7;
inline LL read(){register LL x=0,f=1;register char c=getchar();while(c<48||c>57){if(c=='-')f=-1;c=getchar();}while(c>=48&&c<=57)x=(x<<3)+(x<<1)+(c&15),c=getchar();return f*x;
}const int N=20;
const int MAXN=1<<N;
const int MAXM=1e5+5;LL a[MAXN],b[MAXN];
char s[N][MAXM];
int n,m,len;inline void FWT(LL *A,int type){for(int i=1;i<len;i<<=1)for(int j=0;j<len;j+=(i<<1))for(int k=0;k<i;k++){LL x=A[j+k],y=A[j+i+k];A[j+k]=x+y,A[j+i+k]=x-y;if(type==-1) A[j+k]/=2,A[j+i+k]/=2;}
}int main(){n=read(),m=read();len=1<<n;for(int i=1;i<=n;i++) scanf("%s",s[i]+1);for(int i=1;i<=m;i++){int x=0;for(int j=1;j<=n;j++) x=(x<<1)+s[j][i]-'0';a[x]++;}for(int i=0;i<len;i++) b[i]=b[i>>1]+(i&1);for(int i=0;i<len;i++) b[i]=min(b[i],n-b[i]);FWT(a,1);FWT(b,1);for(int i=0;i<len;i++) a[i]*=b[i];FWT(a,-1);LL ans=a[0];for(int i=1;i<len;i++) ans=min(ans,a[i]);printf("%lld\n",ans);
}