[CERC2016]Bipartite Blanket

题目

传送门 to DarkBZOJ

思路

无论怎么想，都完全不可做啊。主要是点权和 $⩾t$ 的限制，让我们不得不枚举。然而有什么办法，能够在枚举 $\mathfrak{X}$ 部的点集时，求出一个点权和的后缀中 $\mathfrak{Y}$ 部的可行点集？

于是我开始瞎 $jb$ 画图。其间还考虑过，始终维护所有可行 $\mathfrak{Y}$ 部点集，发现这样的时间复杂度根本没有保障……

直到我画了一张图，$\mathfrak{X}$ 部和 $\mathfrak{Y}$ 部选择了的点之间没有任何边，所有边都连向外面。那就是在外面乱选嘛。试试放几条边进来呢？发现也并没有什么问题。那么是不是说，只要两边选择的点在原图上分别存在完备匹配，就存在一个匹配同时覆盖两边的点呢？

一旦想到这个结论，很轻易就证出来了。考虑调整法，先找出一个覆盖 $\mathfrak{X}$ 部的 $A$ 集合的匹配，不妨记它的边是 “红边”，再找出覆盖 $\mathfrak{Y}$ 部的 $B$ 集合的匹配，记它为 “绿边”。根据匹配的定义，一个点的邻边中，最多有一条红边、一条绿边。

既然度数只有 $2$，对于每一个连通块，要么是环，要么是链。如果是环，只保留其中的红边或者绿边，显然可以覆盖这个连通块；如果是链，并且长度为奇数，那就保留第一个颜色（端点的邻边的颜色）的边，就可以覆盖这个连通块；如果是长度为偶数的链，则两个端点同在 $\mathfrak{X}$ 或 $\mathfrak{Y}$ 部，而邻边的颜色不同，所以必定有一个是不需要被覆盖的，保留另一个（必须被覆盖的点）的邻边颜色的所有边。

所以我们只需要对于两边分别判定有无完备匹配，$\mathrm{Hall}$ 定理轻取。时间复杂度 $\mathcal{O}(n\cdot 2^n)$ 。

代码

我调了一天，错误竟然在于：读入时，为了方便，我默认是从高位到低位。本来这没有什么问题，因为图是同构的；问题在于后面要输入点权，必须要把点对应起来！

期间我重构了一次，无任何进展……要不是为了输出中间信息跟 std 比对，我根本没意识到前面我默认将编号翻转的问题……

#include <cstdio> // XJX yyds!!!
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <cctype>
using namespace std;
# define rep(i,a,b) for(int i=(a); i<=(b); ++i)
# define drep(i,a,b) for(int i=(a); i>=(b); --i)
typedef long long int_;
inline int readint(){
	int a = 0, c = getchar(), f = 1;
	for(; !isdigit(c); c=getchar())
		if(c == '-') f = -f;
	for(; isdigit(c); c=getchar())
		a = (a<<3)+(a<<1)+(c^48);
	return a*f;
}
inline int readBin(){
	int a = 0, c = getchar();
	for(; '0'!=c&&c!='1'; c=getchar());
	for(; '0'==c||c=='1'; c=getchar())
		a = (a<<1)^(c^48); // binary
	return a;
}
void writeBin(int x){
	if(x>>1) writeBin(x>>1);
	putchar((x&1)^48);
}
void writeint(int x){
	if(x > 9) writeint(x/10);
	putchar((x-x/10*10)^48);
}

const int MAXN = 20;
struct Node{
	int sum; bool dp;
	bool operator < (const Node &t) const {
		return sum < t.sum;
	}
};
struct Shit{
	Node node[1<<MAXN];
	void solve(int g[],int n){
		node[0].dp = true;
		node[0].sum = g[0] = 0;
		rep(S,1,(1<<n)-1){
			node[S].sum = node[S&(S-1)].sum+node[S&-S].sum;
			g[S] = g[S&(S-1)] bitor g[S&-S];
			node[S].dp = (__builtin_popcount(g[S]) >= __builtin_popcount(S));
			rep(i,0,n-1) node[S].dp = (node[S].dp
				and (!(S>>i&1) or node[S^(1<<i)].dp));
		}
		sort(node,node+(1<<n)); // sort by sum
	}
};

int_ calc(Node *a,int n,Node *b,int m,int bound){
	Node *it = b+m; int_ res = 0;
	const Node *end_a = a+n;
	for(int cnt=0; a!=end_a; ++a){
		while(it != b && ((it-1)->sum)+(a->sum) >= bound)
			-- it, cnt += int(it->dp);
		res += (a->dp)*cnt;
	}
	return res;
}

Shit A, B;
int ga[1<<MAXN], gb[1<<MAXN];
int main(){
	int n = readint(), m = readint();
	rep(i,0,n-1) ga[1<<i] = readBin();
	rep(i,0,n-1) A.node[1<<i].sum = readint();
	A.solve(ga,n); // reduce Cache-Miss
	rep(i,0,n-1) rep(j,0,m-1)
		gb[1<<j] ^= (ga[1<<i]>>j&1)<<i;
	drep(i,m-1,0) B.node[1<<i].sum = readint();
	B.solve(gb,m); // automatically sort
	printf("%lld\n",calc(A.node,1<<n,B.node,1<<m,readint()));
	return 0;
}