CF662C Binary Table

题解

观察数据范围，发现 n n n 很小， m m m 很大， m m m 大约在 2 n 2^n 2n 级别，这很明显地启示我们把01矩阵转化为长度为 m m m 的数列来想。

把行和列颠倒过来显然不影响结果。这个时候我们不妨把每一行的01序列看作一个 2 n 2^n 2n 以内的数的二进制表示，那么对某一列的操作相当于把每个数都异或上一个 2 的次幂，对所有列的操作可以等价于对每个数都异或上一个 [ 0 , 2 n ) [0,2^n) [0,2n) 的值。

现在我们假设这个值是固定的，那么就只剩下行的操作。这个时候每个数显然可以独立判断是否反转，往1的个数少的那边转即可。

由此我们可以形式化地写出答案：设 f ( x ) f(x) f(x) 表示数 x x x 进行了0/1次反转后的最少的1的数量，长度为 m m m 的数列 a i a_i ai​ 标号为 0 ∼ m − 1 0\sim m-1 0∼m−1，那么有
A n s = min ⁡ x ∈ [ 0 , 2 n ) { ∑ i = 0 m − 1 f ( a i   x o r   x ) } Ans=\min_{x\in [0,2^n)}\{\sum_{i=0}^{m-1}f(a_i \,xor\,x)\} Ans=x∈[0,2n)min​{i=0∑m−1​f(ai​xorx)}

这好像有点像可以异或卷积的样子？我们不妨把式子再变一下：设 b i b_i bi​ 表示数列 a a a 中数 i i i 出现的次数，那么
A n s = min ⁡ x ∈ [ 0 , 2 n ) { ∑ i = 0 2 n − 1 f ( i   x o r   x ) ⋅ b i } Ans=\min_{x\in [0,2^n)}\{\sum_{i=0}^{2^n-1}f(i \,xor\,x)\cdot b_i\} Ans=x∈[0,2n)min​{i=0∑2n−1​f(ixorx)⋅bi​}
由异或的性质可得
A n s = min ⁡ x ∈ [ 0 , 2 n ) { ∑ i   x o r   j = x f ( j ) ⋅ b i } Ans=\min_{x\in [0,2^n)}\{\sum_{i\,xor\,j=x}f(j)\cdot b_i\} Ans=x∈[0,2n)min​{ixorj=x∑​f(j)⋅bi​}
这样就完全是异或卷积的样子了，直接做一遍异或卷积即可。

代码

#include<bits/stdc++.h>//JZM yyds!!
#define ll long long
#define uns unsigned
#define IF (it->first)
#define IS (it->second)
#define END putchar('\n')
using namespace std;
const int MAXN=(1<<20)+5;
const ll INF=1e18;
inline ll read(){
	ll x=0;bool f=1;char s=getchar();
	while((s<'0'||s>'9')&&s>0){if(s=='-')f^=1;s=getchar();}
	while(s>='0'&&s<='9')x=(x<<1)+(x<<3)+(s^48),s=getchar();
	return f?x:-x;
}
int ptf[30],lpt;
inline void print(ll x,char c='\n'){
	if(x<0)putchar('-'),x=-x;
	ptf[lpt=1]=x%10;
	while(x>9)x/=10,ptf[++lpt]=x%10;
	while(lpt)putchar(ptf[lpt--]^48);
	putchar(c);
}

const ll MOD=1e9+7;//习惯性取模
int n,m,k,in[MAXN];
char s[MAXN];
ll a[MAXN],b[MAXN],c[MAXN],ans;
inline void FWTXOR(ll*a,int n,int inv){
	ll in2=inv>0?1:((MOD+1)>>1),a0,a1;
	for(int k=n;k>1;k>>=1)
		for(int i=0,d=k>>1;i<n;i+=k)
			for(int j=i;j<i+d;j++)
				a0=a[j],a1=a[j+d],a[j]=(a0+a1)*in2%MOD,a[j+d]=(a0-a1+MOD)*in2%MOD;
}
signed main()
{
	m=read(),n=read();
	for(int j=0;j<m;j++){
		scanf("%s",s);
		for(int i=0;i<n;i++)if(s[i]=='1')in[i]|=(1<<j);
	}
	k=(1<<m);
	for(int i=0;i<n;i++)a[in[i]]++;
	for(int i=0;i<k;i++)b[i]=b[i>>1]+(i&1);
	for(int i=0;i<k;i++)b[i]=min(b[i],m-b[i]);
	FWTXOR(a,k,1),FWTXOR(b,k,1);
	for(int i=0;i<k;i++)c[i]=a[i]*b[i]%MOD;
	FWTXOR(c,k,-1);
	ans=n*m;
	for(int i=0;i<k;i++)ans=min(ans,c[i]);
	print(ans);
	return 0;
}