传送门

这题需要一个引理:一个点集$C=A\cup B$($A$为左边的点集,$B$为右边的点集)能被某个匹配覆盖,当且仅当$A$与右边的某个大小相等的点集$A'$之间存在完美匹配,且$B$与左边的某个大小相等的点集$B'$之间存在完美匹配。

证明大概是这样的:我们构造一个有向图,对于$A$到$A'$之间的匹配,我们从左往右连边,对于$B$到$B'$的匹配,我们从右往左连边。由于每个点入度、出度都至多为$1$,所以这个有向图一定是由一些环和链组成的。环的话一定是偶环,我们每两个点连一条匹配边就行了。链的末端一定不在$C$中,如果链长是偶数就两两连边,否则就可以不管最后一个点了。

有这个引理就好做了,我们直接用Hall定理判断两边点集的每一个子集符不符合引理的条件,然后把所有符合条件的排个序,双指针扫一遍就行了。

#include <bits/stdc++.h>
#define MAXN 30
#define MAXS 1100000
#define LL long long
#define lowbit(x) (x&(-x))
using namespace std;

int n,m;
int g[MAXN][MAXN];
int v1[MAXN],v2[MAXN],lim;
vector<int> s1,s2;

void gao1(){
    static int t[MAXN],h[MAXS],f[MAXS],s[MAXS];
    for(int i=1;i<=n;i++){
        t[i]=0;
        for(int j=1;j<=m;j++)
            if(g[i][j]) t[i]|=1<<(j-1);
    }
    s[0]=h[0]=0; f[0]=1;
    int maxs=1<<n;
    for(int i=1;i<maxs;i++){
        f[i]=1;
        s[i]=0;
        int c1=0,c2=0;
        for(int j=1;j<=n;j++)
            if(i&(1<<(j-1))){
                h[i]=h[i^(1<<(j-1))]|t[j];
                if(!f[i^(1<<(j-1))]) f[i]=0;
                s[i]+=v1[j];
                c1++;
            }
        for(int j=1;j<=m;j++)
            if(h[i]&(1<<(j-1)))
                c2++;
        if(c2<c1) f[i]=0;
    }
    for(int i=0;i<maxs;i++) if(f[i]) s1.push_back(s[i]);
}

void gao2(){
    static int t[MAXN],h[MAXS],f[MAXS],s[MAXS];
    for(int i=1;i<=m;i++){
        t[i]=0;
        for(int j=1;j<=n;j++)
            if(g[j][i]) t[i]|=1<<(j-1);
    }
    s[0]=h[0]=0; f[0]=1;
    int maxs=1<<m;
    for(int i=1;i<maxs;i++){
        f[i]=1;
        s[i]=0;
        int c1=0,c2=0;
        for(int j=1;j<=m;j++)
            if(i&(1<<(j-1))){
                h[i]=h[i^(1<<(j-1))]|t[j];
                if(!f[i^(1<<(j-1))]) f[i]=0;
                s[i]+=v2[j];
                c1++;
            }
        for(int j=1;j<=n;j++)
            if(h[i]&(1<<(j-1)))
                c2++;
        if(c2<c1) f[i]=0;
    }
    for(int i=0;i<maxs;i++) if(f[i]) s2.push_back(s[i]);
}

int main(){
#ifdef DEBUG
    freopen("4788.in","r",stdin);
#endif
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        static char str[MAXN];
        scanf("%s",str+1);
        for(int j=1;j<=m;j++) g[i][j]=(str[j]=='1');
    }
    for(int i=1;i<=n;i++) scanf("%d",v1+i);
    for(int i=1;i<=m;i++) scanf("%d",v2+i);
    scanf("%d",&lim);
    gao1();
    gao2();
    sort(s1.begin(),s1.end());
    sort(s2.begin(),s2.end());
    LL ans=0;
    int now=s2.size()-1;
    for(int i=0;i<s1.size();i++){
        while(now>=0 && s1[i]+s2[now]>=lim) now--;
        ans+=s2.size()-1-now;
    }
    printf("%lld\n",ans);
    return 0;
}