本文主要是介绍CROC 2016 - Final Round [Private, For Onsite Finalists Only] C. Binary Table（FWT），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目链接：http://codeforces.com/contest/662/problem/C
首先将矩阵按列压成二进制，G[i]表示某一列为状态i时最小的1的数目，cnt[i]表示状态i时1的个数，按行枚举翻转状态j，则在状态i下，1的最小的数目为sigma(cnt[i]*G[i^j])，因为i^(i^j)=j，所以可以看作一个异或卷积的形式，采用fwt进行加速即可。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=(1<<20)+5;
const int M=1e5+5;
ll G[MAXN],F[MAXN],T[MAXN];
char s[M];
namespace fwt
{void FWT(ll a[],int n){for(int d=1;d<n;d<<=1)for(int m=d<<1,i=0;i<n;i+=m)for(int j=0;j<d;j++){ll x=a[i+j],y=a[i+j+d];a[i+j]=x+y,a[i+j+d]=(x-y);//and:a[i+j]=x+y;//or:a[i+j+d]=x+y;}}void UFWT(ll a[],int n){for(int d=1;d<n;d<<=1)for(int m=d<<1,i=0;i<n;i+=m)for(int j=0;j<d;j++){ll x=a[i+j],y=a[i+j+d];a[i+j]=(x+y)/2,a[i+j+d]=(x-y)/2;//and:a[i+j]=x-y;//or:a[i+j+d]=y-x;}}void solve(ll a[],ll b[],int n){FWT(a,n);FWT(b,n);for(int i=0;i<n;i++) a[i]=a[i]*b[i];UFWT(a,n);}
}int main()
{//freopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){scanf("%s",s+1);for(int j=1;j<=m;j++){T[j]|=((s[j]-'0')<<(i-1));}}for(int j=1;j<=m;j++){F[T[j]]++;}int tot=(1<<n);for(int i=0;i<tot;i++){int num=__builtin_popcount(i);G[i]=min(num,n-num);}fwt::solve(G,F,tot);int ans=1e9;for(int i=0;i<tot;i++){ans=min(ans,(int)G[i]);}printf("%d\n",ans);return 0;
}
这篇关于CROC 2016 - Final Round [Private, For Onsite Finalists Only] C. Binary Table（FWT）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
