「CF662C」 Binary Table

题目链接

题目所给的 \(n\) 很小，于是我们可以考虑这样一种朴素做法：暴力枚举第 \(i\) 行是否翻转，这样每一行的状态就确定了，这时取每一列 \(0/1\) 个数较小的数字即可（因为每一列也可以翻转）。这样的时间复杂度是 \(O(m\cdot2^n)\)。

但是显然这样过不了。

我们发现表格的具体行列对我们的答案是没有影响的。即我们只需要知道状态为 \(x\) 的行或者状态为 \(x\) 的列的个数即可。由于 \(n\le20\)，这启发我们对于每一列进行状态压缩。

于是我们定义：\(f_S\) 表示列状态为 \(S\) 的列的个数，同时定义 \(g_S\) 为列状态为 \(S\) 的列中 \(0/1\) 个数中小的一个。显然 \(f,g\) 两个数组都可以在可以接受的时间范围内预处理出来。

对于翻转情况，我们用一个数 \(x\) 表示，若二进制下第 \(i\) 位为 \(1\)，则代表第 \(i\) 行翻转。

于是有当翻转状态为 \(x\) 时，有

\[Ans_x=\sum_{i=0}^{2^n-1}f_ig_{i\oplus x}
\]

其中 \(\oplus\) 代表按位异或。

简单变形，我们可以得到

\[Ans_x=\sum_{i=0}^{2^n-1}\sum_{j=0}^{2^n-1}[i\oplus x=j]f_ig_j
\]

由于异或具有交换律，于是有

\[Ans_x=\sum_{i=0}^{2^n-1}\sum_{j=0}^{2^n-1}[i\oplus j=x]f_ig_j
\]

这就是集合幂卷积中异或卷积的标准形式，直接使用 \(\texttt{FWT}\) 优化计算即可。时间复杂度为 \(O(n2^n)\)。

代码很简洁，如下：

#include<bits/stdc++.h>

using namespace std;

const int maxn=2e6+5;

long long num[maxn],f[maxn],g[maxn];

int n,m;

inline void XOR(long long *f,int tmp){

	for(int o=2,k=1;o<=n;o<<=1,k<<=1){

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

			for(int j=0;j<k;++j){

				long long a=f[i+j],b=f[i+j+k];

				if(tmp) f[i+j]=a+b,f[i+j+k]=a-b;

				else f[i+j]=(a+b)>>1,f[i+j+k]=(a-b)>>1;

			}

		}

	}

}

int main(){

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

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

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

			int x;scanf("%1d",&x);

			num[j]+=x*(1<<i-1);

		}

	}

	for(int i=1;i<=m;++i) ++f[num[i]];

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

		int x=i;

		while(x) x=(x-1)&x,++g[i];

		g[i]=min(g[i],n-g[i]);

	}

	n=(1<<n);

	XOR(f,1),XOR(g,1);

	for(int i=0;i<n;++i) f[i]=f[i]*g[i];

	XOR(f,0);

	long long ans=(1<<30);

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

	printf("%lld\n",ans);

	return 0;

}

巴特西

「CF662C」 Binary Table

「CF662C」 Binary Table

最新文章

热门文章