题解：AT_abc396_g [ABC396G] Flip Row or Col

提供一个 FWT 做法。

首先，我们看到输入的

W

十分小，于是考虑

2^W

枚举每一列是否翻转的状态，记为

s

。对于第

i

行，将这一行的数改为用二进制表示，记为

B_i

。

我们设

\text{popcount(x)}

表示

x

在二进制下

1

的个数，

\oplus

表示异或运算，那么说如果

W-\text{popcount}(B_i\oplus s)<\text{popcount}(B_i\oplus s)

，就说明这一行全部异或一产生的贡献会更小，于是选择异或一。

设

f(s)

表示当每一列是否翻转的状态为

s

时矩阵中一的个数最少是多少，那么容易得出:

f(s)=\sum_{i=1}^H\min(\text{popcount}(B_i\oplus s),W-\text{popcount}(B_i\oplus s))\\ ans=\min_{s=0}^{2^W-1}f(s)

现在我们考虑如何快速求出所有

f(s)

。

设

h(s)=\min(\text{popcount}(s),W-\text{popcount}(s))

，

g(s)=\sum_{i=1}^{H}[B_i=s]

。

于是我们考虑化繁一下式子：

\begin{aligned} f(s)=&\sum_{i=1}^Hh(B_i\oplus s)\\ =&\sum_{i=1}^H\sum_{y=0}^{2^W-1}[B_i\oplus s=y]h(y)\\ =&\sum_{y=0}^{2^W-1}h(y)\sum_{i=1}^H[B_i\oplus y=s]\\ =&\sum_{y\oplus z=s}h(y)g(z) \end{aligned}

然后就可以用 FWT 快速求解了。

code

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<18)+10;
int m,n;
ll A[N],B[N];
ll a[N],b[N];
void xorr(ll*f,double type)
{
	for(int len=2;len<=n;len<<=1)
	{
		int mid=len>>1;
		for(int i=0;i<n;i+=len)
		{
			for(int j=0;j<mid;j++)
			{
				f[i+j]+=f[i+j+mid];
				f[i+j+mid]=f[i+j]-2*f[i+j+mid];
				f[i+j]=f[i+j]*type,f[i+j+mid]=f[i+j+mid]*type;
			}
		}
	}
}
int we;
string s;
#define popcount(x) __builtin_popcount(x)
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	cin>>we>>m,n=1<<m;
	for(int i=1;i<=we;i++){
		cin>>s;
		int sum=0;
		for(int i=0;i<m;i++) sum=sum+((s[i]-'0')<<i);
		a[sum]++;
	}
	for(int i=0;i<n;i++) b[i]=min(popcount(i),popcount(n-1-i));
	xorr(a,1),xorr(b,1);
	for(int i=0;i<n;i++) a[i]=a[i]*b[i];
	xorr(a,0.5);
	ll ans=1e18;
	for(int i=0;i<n;i++) ans=min(ans,a[i]); 
	cout<<ans<<"\n";
	return 0;
}

题解：AT_abc396_g [ABC396G] Flip Row or Col

文章操作

code

相关推荐

评论

题解：AT_abc396_g [ABC396G] Flip Row or Col