P3679 [CERC2016] Bipartite Blanket

In a bipartite graph, all vertices are split into two disjoint sets $A$ and $B$, and every edge connects some vertex in $A$ to some vertex in $B$. A matching is a set of edges such that no two edges share an endpoint. We say a matching $M$ covers a vertex set $V$ if and only if every vertex in $V$ is an endpoint of at least one edge in $M$. Given a bipartite graph where each vertex has a positive integer weight, define the weight of a vertex set as the sum of the weights of its vertices. Given a parameter $t$, count how many vertex sets $V$ satisfy that the weight of $V$ is at least $t$, and $V$ is covered by at least one matching $M$.

The first line contains two positive integers $n, m$, denoting the number of vertices in set $A$ and set $B$, respectively. The next $n$ lines each contain $m$ binary characters '0' or '1'. In the $i$-th row and the $j$-th column, a $1$ indicates there is an edge between $A_i$ and $B_j$. The next line contains $n$ positive integers $v_1, v_2, \cdots, v_n$, denoting the weight of each vertex in $A$. The next line contains $m$ positive integers $w_1, w_2, \cdots, w_m$, denoting the weight of each vertex in $B$. The last line contains a positive integer $t$, representing the parameter $t$.

Output a single integer on one line, the number of vertex sets that satisfy the condition.

$1 \leq n, m \leq 20$, $1 \leq v_i, w_i \leq 10^7$, $1 \leq t \leq 4 \times 10^8$. Translated by ChatGPT 5