Apagando las luces P37448

Las clases del professor Oak son una mezcla de ejemplos dibujados en la pizarra y de códigos tecleados con dos dedos y mostrados con el proyector. Para poder hacer estas clases, el pobre estudiante más cercano a los interruptores tiene que ir apagando y encendiendo las luces del aula.

Hasta aquí la historia es real, ahora empieza la ficción. Hay n luces y m interruptores. Los operarios de la FME han mezclado los cables, y ahora cada interruptor cambia el estado (de encendido a apagado, o de apagado a encendido) de diversas luces a la vez. Dado el estado inicial de cada luz, y las luces cambiadas por cada interruptor, ¿de cuantas maneras se pueden apagar todas las luces? Como pulsar el mismo interruptor dos veces sería como no hacer nada, cada interruptor se puede pulsar como mucho una vez.

Entrada

La entrada consiste en diversos casos, cada uno con n, seguida de los estados iniciales de las n luces en orden (un 0 indica apagada, un 1 indica encendida), seguidos de m, seguida de la información de los m interruptores: Para cada uno, tenemos el número f de luces a las cuales afecta, seguido de f números diferentes entre 0 y n−1. Suponed 1 ≤ n ≤ 100, 1 ≤ m ≤ 15, y 1 ≤ f ≤ n.

Salida

Para cada caso, escribid cuantas combinaciones de los interruptores apagan todas las luces.

Pista

La solución esperada és un backtracking sencillo.