FWT板子w

就是一个显然的做法就是枚举哪些行翻转，然后对于每一列贪心取翻转或者不翻即min(count(i),n-count(i))

这样肯定是过不去的 我们来考虑优化

我们记录数组F表示对于一个数i它的较优翻转 即上面的那个柿子

然后再记录一个数组表示原来的矩阵中每一列的计数 cnt[i]表示将一列看成一个二进制数 这个数是i的列数

对于答案我们有就是考虑计算贡献 ans[k]表示行的翻转是k

由于是等价于的所以我们可以转化成卷积形式然后套上异或FWT即可

【码风日益毒瘤】代码。

//Love and Freedom.#include
    
     #include
     
      #include
      
       #include
       
        #define inf 20021225#define ll long long#define mxn (1<<20)#define int llusing namespace std;int f[mxn+10],cnt[mxn+10];int ans[mxn+10];void fwt(int *a,int n,int f){	for(int k=2,mid=1;k<=n;k<<=1,mid<<=1)	{		for(int i=0;i
        
         0)	a[i+j] = x+y,a[i+mid+j] = x-y;			else	a[i+j] = (x+y)/2,a[i+mid+j] = (x-y)/2;		}	}}char ch[100010];int mp[21][100010];int count(int x){	int ct=0;	while(x)	x=x&(x-1),ct++;	return ct;}signed main(){	int n,m;	scanf("%lld%lld",&n,&m);	for(int i=0;i
         
          >=1; cnt[tmp]++; } int qwq=0,top=1<