시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 1024 MB887100.000%

문제

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?

입력

Den första raden innehåller tre heltal: $2\le N \le 15$, antalet deltagare, $2\le K \le 10$, antalet djurarter, och $2 \le M\le 5$, 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.

출력

Programmet ska skriva ut ett heltal, antal sätt Esmeralda kan placera ut djur på. För givna indata kommer svaret aldrig överstiga 2 miljarder.

예제 입력 1

3 4 0

예제 출력 1

36

예제 입력 2

4 5 2
BE
BADC

예제 출력 2

18

예제 입력 3

9 8 3
AC
CGD
BEFD

예제 출력 3

2235978

힌트

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.

출처

Olympiad > Swedish Olympiad in Informatics > 2020 > Qualification 3번

  • 문제를 만든 사람: Fredrik Ekholm, Per Söderhjelm