[CodeForces 663E] - Binary Table(FWT)

题目

Codeforces 题目链接

分析

大佬博客，写的很好

本蒟蒻就不赘述了，就是一个看不出来的异或卷积

精髓在于

AC code

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;//必须用long long,过程中可能炸int

const int MAXN = 1<<20;

const LL INF = 1e18;

const int MAXM = 1e5 + 1;

int n, m, num[MAXM];

LL A[MAXN], B[MAXN];

char str[20][MAXM];

inline int calc(int s)

{

	int ret = 0;

	while(s) ++ret, s -= s&(-s);

	return min(n - ret, ret);

}

inline void FWT(LL arr[], const int &len, const int &flg)

{

	register LL x, y;

	for(register int i = 2; i <= len; i<<=1)

		for(register int j = 0; j < len; j += i)

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

			{

				x = arr[k], y = arr[k + i/2];

				if(~flg) arr[k] = x + y, arr[k + i/2] = x - y;

				else arr[k] = (x + y) / 2, arr[k + i/2] = (x - y) / 2;

			}

}

int main ()

{

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

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

		scanf("%s", str[i]);

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

	{

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

			num[i] |= (str[j][i] - '0') << j;

		++A[num[i]];

	}

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

		B[i] = calc(i);

	FWT(A, 1<<n, 1);

	FWT(B, 1<<n, 1);

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

		A[i] *= B[i];

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

	LL Ans = INF;

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

		Ans = min(Ans, A[i]);

	printf("%I64d\n", Ans);

}