题目描述

有一个\(n\)行\(m\)列的表格，每个元素都是\(0/1\)，每次操作可以选择一行或一列，把\(0/1\)翻转，即把\(0\)换为\(1\)，把\(1\)换为\(0\)。请问经过若干次操作后，表格中最少有多少个\(1\)。

题解

但凡跟状态转移扯上一点关系的题目就没我什么事了……

首先，我们可以枚举每一行是否反转，然后每一次就可以\(O(m)\)的计算出答案，然而这样的复杂度是\(O(2^nm)\)的，会挂

我们设\(a[S]\)表示状态为\(S\)的列有多少个，\(b[S]\)表示状态\(S\)中\(0\)和\(1\)的个数中较小的那一个，设当前的行状态为\(now\)，可以有如下转移\[ans=\sum_{i=0}^{2^n}a[i]\times b[i⊕now]\]

因为有\(i⊕i⊕now=now\)，所以转移可以写成如下形式\[ans[now]=\sum_{i⊕j=now}a[j]*b[j]\]

用\(FWT\)优化即可，复杂度为\(O(2^n\log(2^n))=O(n*2^n)\)

//minamoto#include
    
     #define R register#define ll long long#define fp(i,a,b) for(R int i=a,I=b+1;i
     
      I;--i)#define go(u) for(int i=head[u],v=e[i].v;i;i=e[i].nx,v=e[i].v)template
      
       inline bool cmin(T&a,const T&b){return a>b?a=b,1:0;}using namespace std;const int N=(1<<20)+5;char s[N];int sz[N],g[N],n,m,lim;ll A[N],B[N],ans=1e9;void FWT(ll *A,int ty){    for(R int mid=1;mid
       
        <<=1)        for(R int j=0;j
        
         <<1))            for(R int k=0;k
         
          >1]+(i&1); fp(i,0,lim-1)B[i]=min(sz[i],n-sz[i]); FWT(A,1),FWT(B,1);fp(i,0,lim-1)A[i]=A[i]*B[i]; FWT(A,-1);fp(i,0,lim-1)cmin(ans,A[i]); printf("%d\n",ans);return 0;}