Problem H
Light Switches
You’ve been given the auspicious role of lead assistant light-switcher by the Heliological Counterfeiting Planning Committee (HCPC), and it’s almost time to fake the most important sun-based event of the year—a total solar eclipse. Your superior, of course, is in charge of progressively switching the lights off during the event, which leaves the important role of writing a program to plan the event to you. Knowing that this will be trivial, you’ve wisely procrastinated on making said program until the last available moment, which it now is.
A switch can be either on or off and controls a single light. A single light can, however, be controlled simultaneously by multiple switches. A light is on if an odd number of switches that control it are flipped on, and it is otherwise off. A bank of switches is a set of switches all grouped together in a single location on a wall.
You’ve already masterfully delegated the task of making light switching easier to the other assistant light-switchers, and they’ve come back with a brilliant tool to switch all of the switches in a single bank on or off simultaneously, which they call a ‘stick’. However, it only occurs to you—which is probably why you were made lead assistant—that it might not even be possible to create a particular state of lights being on and off using such a tool! You’ll need to look at every single step of the plan and make sure that there’s at least one way to set all of the switches in each bank consistently to enable the desired combination of lights.
Input
The input consists of three sections separated by blank lines. The first section has the values of $m$ ($0 \leq m \leq 16$), the number of banks, and $n$ ($1 \leq n \leq 50$), the number of lights you need to control, separated by a space. The second section contains $m$ lines. Each line contains a list of numbers, representing a bank of switches. The length of this list $k$ will be at least $1$ and at most $3 \cdot n$. Each value in the list specifies the light controlled by one switch in the bank; the lights are numbered from $0$ to $n-1$. The third section is a single line containing $n$ space-separated values. The $i$-th value will either be $1$ or $0$, representing that the $i$-th light should be on or off respectively.
Output
Output the number of distinct positions that the switches could be in such that each bank of switches is either all on or all off while producing the given state of lights.
Explanation of Sample Inputs
In Sample Input 1, there are two banks of switches; each bank contains one switch that controls light $0$ and one switch that controls light $1$. Given this setup, it is impossible to create the desired configuration of lights (namely, light $0$ being on and light $1$ being off) since all the switches in a bank must be switched on or off together. We could turn both lights on (by flipping both switches in either one of the two banks) or have them both off (either by leaving all the switches off, or by turning on the switches in both banks), but not one of each.
Sample Input 2 is similar, but this time the first bank only has a switch for light $0$. If we turn it on and leave the other bank off, we reach the desired configuration of lights. In Sample Input 3, we want the lights the other way, which we can achieve by turning all the switches on, resulting in light $1$ being on but light $0$ being off.
| Sample Input 1 | Sample Output 1 |
|---|---|
2 2 0 1 0 1 1 0 |
0 |
| Sample Input 2 | Sample Output 2 |
|---|---|
2 2 0 0 1 1 0 |
1 |
| Sample Input 3 | Sample Output 3 |
|---|---|
2 2 0 0 1 0 1 |
1 |
| Sample Input 4 | Sample Output 4 |
|---|---|
6 2 0 0 0 0 0 0 1 0 1 |
16 |
| Sample Input 5 | Sample Output 5 |
|---|---|
2 2 0 0 1 1 0 0 |
4 |
