听说这是一道$ Tourist$现场没出的题

题意：

给定$n*m的 01$矩阵，可以任意反转一行/列($0$变$1$，$1$变$0$)，求最少$ 1$的数量

$ n<=20 \ m<=100000$

---

$ Solution$

考虑暴力

枚举每一行反转/不反转

预处理$ g(s)$表示某状态为$ s$的列的最少$ 1$的数量

显然$ g(s)=min(popcount(s),n-popcount(s))$

枚举每行是否反转之后直接$ O(m)$计算即可

时间复杂度$ O(2^n m)$，无法通过这题

 

容易发现瓶颈在于暴力枚举行状态之后无法快速计算答案

我们令$ f(s)$表示列状态为$ s$的列的出现次数，$ F(s)$表示行反转状态为$ s$的时候的答案

转移有$ F(s)=\sum\limits_{i=0}^{2^n-1}f(i)g(i \ xor \ s)$

由于$ i \ xor \ i \  xor \  s = s$

所以可以化简为$ F(s)=\sum\limits_{i \ xor \ j =s}f(i)g(j)$

是一个$ FWT$卷积的形式

直接$ FWT$优化

时间复杂度：$ O(nm+2^n n)$

注意$ FWT$过程中可能要开$ long \ long$

---

$ my \ code:$

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #define rt register int#define ll long longusing namespace std;inline ll read(){ ll x = 0; char zf = 1; char ch = getchar(); while (ch != '-' && !isdigit(ch)) ch = getchar(); if (ch == '-') zf = -1, ch = getchar(); while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar(); return x * zf;}void write(ll y){ if(y<0)putchar('-'),y=-y;if(y>9)write(y/10);putchar(y%10+48);}void writeln(const ll y){write(y);putchar('\n');}int i,j,k,m,n,x,y,z,cnt,invn;void fwt(int n,ll *a,int fla){ for(rt i=1;i
            
             <<=1) for(rt j=0;j
             
              <<1) for(rt k=0;k