一、题目
二、解法
结论：如果左部点集 \(A\) 存在完美匹配，右部点集 \(B\) 存在完美匹配，那么存在包含 \(A,B\) 的匹配。
证明：把集合 \(A\) 匹配边染黑，把集合 \(B\) 匹配边染白。
考虑得到的图度数至多 \(2\)，那么可以简单分类讨论：
- 如果连通块是一个环，那么存在用上所有点的匹配方案。
- 如果连通块是长度为奇数的链，那么所有点也都可以用上。
- 如果连通块是长度为偶数的链，那么左部\(/\)右部会多出一个点，考虑这两个点边的颜色不同，所以一定存在一个点不属于 \(A/B\)，就不需要匹配它。
证毕。
判断完美匹配的方法就是 \(\tt Hall\) 定理，两边折半然后拼起来即可，时间复杂度 \(O(2^n\cdot n)\)
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1<<20;
int read()
{
int x=0,f=1;char c;
while((c=getchar())<'0' || c>'9') {if(c=='-') f=-1;}
while(c>='0' && c<='9') {x=(x<<3)+(x<<1)+(c^48);c=getchar();}
return x*f;
}
int n,m,sa[N],sb[N],f[N],cnt[N],wa[N],wb[N];
vector<int> a,b;long long ans;
signed main()
{
n=read();m=read();
for(int i=0;i<n;i++)
for(int j=0;j<m;j++)
{
int x;scanf("%1d",&x);
sa[1<<i]|=x<<j;
sb[1<<j]|=x<<i;
}
for(int i=0;i<n;i++) wa[1<<i]=read();
for(int i=0;i<n;i++) wb[1<<i]=read();
for(int i=0;i<(1<<20);i++)
{
int t=i&(-i);
cnt[i]=cnt[i>>1]+(i&1);
if(i!=t)
{
wa[i]=wa[i-t]+wa[t];
sa[i]=sa[i-t]|sa[t];
wb[i]=wb[i-t]+wb[t];
sb[i]=sb[i-t]|sb[t];
}
}
for(int i=0;i<(1<<n);i++)
{
f[i]=1;
for(int j=0;j<n;j++) if(i>>j&1)
f[i]&=f[i^(1<<j)];
f[i]&=cnt[i]<=cnt[sa[i]];
if(f[i]) a.push_back(wa[i]);
}
for(int i=0;i<(1<<m);i++)
{
f[i]=1;
for(int j=0;j<m;j++) if(i>>j&1)
f[i]&=f[i^(1<<j)];
f[i]&=cnt[i]<=cnt[sb[i]];
if(f[i]) b.push_back(wb[i]);
}
int k=read();
sort(b.begin(),b.end());
for(auto x:a)
ans+=b.end()-lower_bound(b.begin(),b.end(),k-x);
printf("%lld\n",ans);
}