Les vaches veulent former une expédition pour explorer les bois au bord du territoire de Farmer John. Explorer demande plus de compétences que rester dans le pré à brouter.
L’équipe des $C$ vaches ($1 \le C \le 20$) numérotées 1..$C$ doit savoir s’orienter sans se perdre, repousser de grandes créatures méchantes, raconter des blagues pour garder le moral, etc. Chacune des $A$ capacités spéciales ($1 \le A \le 20$), numérotées 1..$A$, doit être possédée par au moins une vache de l’équipe. Certaines n’ont qu’une capacité, beaucoup en ont plusieurs, et certaines sont des profiteuses complètement inutiles.
À partir des vaches et de leurs capacités, calculez le nombre d’équipes distinctes ayant collectivement toutes les capacités données.
Entrée
- Ligne 1 : les entiers $C$ et $A$.
- Lignes 2..$A$+1 : chaque ligne décrit une capacité par des entiers séparés par des espaces. La ligne 2 décrit la capacité 1, la ligne 3 la capacité 2, etc. Le premier entier $K$ ($1 \le K \le C$) est le nombre de vaches la possédant. Les $K$ entiers suivants désignent ces vaches.
Sortie
- Ligne 1 : un entier, le nombre d’équipes d’exploration distinctes possibles.
Exemples
Entrée 1
4 2 2 3 1 1 2
Sortie 1
6
Remarque
Détails de l’entrée
Il y a 4 vaches et 2 capacités. Les vaches 1 et 3 ont la capacité 1, seule la vache 2 a la capacité 2. La vache 4 est assez peu douée.
Détails de la sortie
Les équipes possibles sont $\{1, 2\}$, $\{2, 3\}$, $\{1, 2, 3\}$, $\{1, 2, 4\}$, $\{2, 3, 4\}$ et $\{1, 2, 3, 4\}$.
Auteur du problème : Percy Liang, 2004