Description：

你有一个 $n\times m$ 的 $01$ 矩阵。你可以把任意一行或者一列的 $01$ 取反。求矩阵中最少的 $1$ 的数量。

$n\leqslant 20,m\leqslant 10$

Solution：

既然行数这么少那么就可以枚举行取反的情况，设为 $k$ ，那么就可以 $O(2^nm)$ 求出这个 $k$ 最少的 $1$ 的数量，但是这样显然是会超时的，发现实际上每一行之间都是等价的，那么我们可以设 $a[i]$ 表示状态 $i$ 出现的次数， $b[i]$ 表示状态 $i$ 取反或不取反 $1$ 的较小值，那么如果行的取反情况为 $k$ ，那么有： $$ ans_k=\sum_{i\text{ xor }k=j}a[i]\times b[j] $$ 由异或的性质得上面那个式子等价于： $$ ans_k=\sum_{i\text{ xor }j=k}a[i]\times b[j] $$ 这就是一个 $FWT\_xor$ 的标准形式了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

int n,m;

#define MAXN 21

#define MAXM 100010

int v[MAXN][MAXM];

int getc()

{

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	return c - '0';

}

typedef long long ll;

ll a[1 << MAXN],b[1 << MAXN];

void FWT(ll f[],int l,int type)

{

	for(int i = 2;i <= l;i = i << 1)

	{

		for(int j = 0;j < l;j += i)

		{

			for(int k = j;k < j + i / 2;++k)

			{

				ll u = f[k],t = f[k + i / 2];

				f[k] = u + t;

				f[k + i / 2] = u - t;

				if(type == -1)

				{

					f[k] /= 2;

					f[k + i / 2] /= 2;

				}

			}

		}

	}

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= m;++j)

			v[i][j] = getc();

	for(int i = 1;i <= m;++i)

	{

		int val = 0;

		for(int j = 1;j <= n;++j)

			val = val << 1 | v[j][i];

		++a[val];

	}

	for(int i = 0;i < (1 << n);++i)

	{

		int cnt = 0;

		for(int j = 0;j < n;++j)if(i & (1 << j))++cnt;

		b[i] = min(cnt,n - cnt);

	}

	FWT(a,(1 << n),1);FWT(b,(1 << n),1);

	for(int i = 0;i < (1 << n);++i)a[i] = a[i] * b[i];

	FWT(a,(1 << n),-1);

	ll ans = 9999999999;

	for(int i = 0;i < (1 << n);++i)ans = min(ans,a[i]);

	cout << ans << endl;

	return 0;

}