---

题解

刚刚学习了\(FWT\),然后看到这道题还是想不出来

首先发现\(n\)很小,所以枚举每一行是否翻转是可行的

然后这样以后对于每一列的状态都要异或上行翻转的状态

这样每一列不会对其他列造成影响

就看翻转与不翻转谁优

这样我们就有了\(O(2^nm)\)的做法

这样复杂度太高了

我们发现一列的状态相同的可以合在一起

设\(a[i]\)表示一列的状态为\(i\)的\(0,1\)个数的较小值

\(b[i]\)表示一列状态为\(i\)的有多少个

\(f[i]\)表示行翻转状态为\(i\)时的答案

那么\(f[S]=\sum_{j=i \oplus S}{b[i] * a[j]}\)

但是异或有优秀的对称差的性质啊

\(i \oplus j=k -> i \oplus k=j\)

所以\(f[S]=\sum_{S=i \oplus j}{b[i]*a[j]}\)

题解

#include
    
     #include
     
      #include
      
       #include
       
        # define LL long longconst int M = 4500005 ;const int N = 100005 ;const int INF = 1e9 ;using namespace std ;int n , m , lim ;char s[21][N] ;LL a[M] , b[M] , ans = INF ;inline int Calc(int S) {    int ret = 0 ;    for(int i = 0 ; i < n ; i ++)        if(S & (1 << i))            ++ ret ;    return min(ret , n - ret) ;}inline void FWT_xor(LL *A , int unit) {    for(int mid = 1 ; mid < lim ; (mid <<= 1)) {        int R = (mid << 1) ;        for(int j = 0 ; j < lim ; j += R)             for(int k = 0 ; k < mid ; k ++) {                LL x = A[j + k] , y = A[j + k + mid] ;                A[j + k] = x + y ; ; A[j + k + mid] = x - y ;                if(unit < 0) A[j + k] /= 2 , A[j + k + mid] /= 2 ;            }    }}int main() {    scanf("%d%d",&n,&m) ;     for(int i = 1 ; i <= n ; i ++) scanf("%s",s[i] + 1) ;    for(int i = 0 ; i < (1 << n) ; i ++)         a[i] = Calc(i) ;    for(int i = 1 , S ; i <= m ; i ++) {        S = 0 ;        for(int j = 1 ; j <= n ; j ++)             S = (S << 1) + (s[j][i] - '0') ;        ++ b[S] ;    }    lim = 1 ; while(lim < (1 << n)) lim <<= 1 ;    FWT_xor(a , 1) ; FWT_xor(b , 1) ;    for(int i = 0 ; i < lim ; i ++) b[i] = a[i] * b[i] ;    FWT_xor(b , -1) ;    for(int i = 0 ; i < (1 << n) ; i ++)        ans = min(ans , b[i]) ;    printf("%lld\n",ans) ;    return 0 ;}