Problem C
Zoo
Esmeralda bygger ett zoo med $N$ burar i en lång rad. Varje bur ska fyllas med ett djur. Hon har $K$ olika djurarter att välja på, som vi kallar A, B, C, o.s.v. Hon kan ha flera burar med samma djurart, men inte precis intill varandra. Dessutom vet hon att vissa djur inte trivs bra ihop. Närmare bestämt så finns det $M$ stycken “bråkiga grupper” av djurarter, och Esmeralda vill inte placera två djur ur samma bråkiga grupp i burar intill varandra. På hur många sätt kan Esmeralda placera ut djur i burarna?
Indata
Den första raden innehåller tre heltal $N$ ($2 \le N \le 15$), $K$ ($2 \le K \le 10$) och $M$ ($0 \le M \le 5$): antalet burar, antalet djurarter, och antalet bråkiga grupper.
På var och en av de följande $M$ raderna står en sträng som består av mellan $2$ och $K$ bokstäver: en bråkig grupp av djurarter som parvis inte tolererar varandra. Endast de $K$ första bokstäverna i alfabetet (och endast versaler) kan förekomma i strängarna och en bokstav förekommer inte flera gånger i samma sträng.
Indatan kommer alltid vara så att svaret aldrig överstiger 2 miljarder.
Utdata
Programmet ska skriva ut ett heltal, antal sätt Esmeralda kan placera ut djur på.
Poängsättning
Din lösning kommer att testas på en mängd testfallsgrupper. För att få poäng för en grupp så måste du klara alla testfall i gruppen.
|
Fall |
Poängvärde |
Gränser |
|
$1$ |
$20$ |
$N \le 10$, $K \le 5$, $M=0$ |
|
$2$ |
$40$ |
$N \le 10$, $K \le 5$ |
|
$3$ |
$20$ |
$M \le 1$ |
|
$4$ |
$20$ |
Inga ytterligare begränsningar. |
Förklaring av exempelfall
I det första exemplet trivs alla arter ihop. I första buren kan Esmeralda välja mellan 4 djurarter. För andra och tredje buren finns tre möjligheter vardera, eftersom det inte får vara samma art som i den föregående. Totalt finns $4\cdot 3\cdot 3=36$ möjliga placeringar.
I det andra exemplet vet vi att Babian och Elefant inte får vara intill varandra. Vi vet också att Babian, Antilop, Dingo och Citronfjäril alla är fiender, och inga av dessa kan därför sättas intill varandra. Esmeralda måste sålunda sätta en elefant i varannan bur och välja fritt mellan antilop, dingo och citronfjäril i de övriga. Detta ger 9 möjligheter om hon börjar med elefant och 9 möjligheter om hon börjar med något av de andra djuren.
| Sample Input 1 | Sample Output 1 |
|---|---|
4 5 2 BE BADC |
18 |
| Sample Input 2 | Sample Output 2 |
|---|---|
3 4 0 |
36 |
| Sample Input 3 | Sample Output 3 |
|---|---|
9 8 3 AC CGD BEFD |
2235978 |
