GYM 101173B: Bipartite Blanket

http://codeforces.com/group/NVaJtLaLjS/contest/257177/attachments
题意：
有一个二分图，一个点集合法当且仅当：该点集的【每个点】都属于【某一匹配】。
问这些合法的点集当中，有多少个权值和大于t.
思路：
有一个性质可以证明：如果属于X的一个点集v1属于某个完美匹配，同时属于Y的一个点集v2也存在于完美匹配中，那么v1+v2一定也属于某个完美匹配中。
那么完美分别枚举X和Y中的状态，根据hall定理(https://www.cnblogs.com/dummyummy/p/10311769.html)，判断所有点集是不是属于某个完美匹配，最后一块统计。

#include<bits/stdc++.h>
using namespace std;

int n,m,wx[30],wy[30],coverx[1<<21],covery[1<<21],cnt[1<<21],t;
bool fx[1<<21],fy[1<<21];
vector<int> x,y;

void solve(int n,int *wx,int *coverx,bool *fx,vector<int> &x)
{
    for(int s=0;s<(1<<n);s++)
    {
        fx[s]=1;
        int sum=0;
        for(int i=0;i<n;i++)if(s&(1<<i))
        {
            coverx[s]|=coverx[s^(1<<i)];
            sum+=wx[i];
            fx[s]&=fx[s^(1<<i)];
        }
        if(fx[s] && cnt[s]<=cnt[coverx[s]])x.push_back(sum);
        else fx[s]=0;
    }
}

int main()
{
   // freopen("input.in","r",stdin);
    cin>>n>>m;
    char str[30];
    for(int i=0;i<n;i++)
    {
        scanf("%s",str);
        for(int j=0;j<m;j++)if(str[j]=='1')
            coverx[1<<i]|=(1<<j),covery[1<<j]|=(1<<i);
    }
    for(int i=0;i<n;i++)cin>>wx[i];
    for(int j=0;j<m;j++)cin>>wy[j];
    cin>>t;
    for(int s=0;s<(1<<20);s++)cnt[s]=cnt[s>>1]+(s&1);
    solve(n,wx,coverx,fx,x);
    solve(m,wy,covery,fy,y);
    sort(x.begin(),x.end());
    long long ans=0;
    for(int i=0;i<y.size();i++)
    {
        ans+=x.end()-lower_bound(x.begin(),x.end(),t-y[i]);
    }
    cout<<ans<<endl;
    return 0;
}