루미 알고리즘

#1506실버Zoo

PO 2020 학교 예선코딩출제 Fredrik Ekholm, Pär Söderhjelm스웨덴어 원문이 문제가 어렵다면 — 배우는 순서 보기

스웨덴어 원문입니다. 원문의 수식·표를 글자로 옮겨 모양이 다를 수 있습니다. 정확한 내용은 원문 페이지에서 확인하세요. 원문 페이지 열기 (새 창)

Problem

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 ≤ N ≤ 15), K (2 ≤ K ≤ 10) och M (0 ≤ M ≤ 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.

FallPoängvärdeGränser
120N ≤ 10, K ≤ 5, M=0
240N ≤ 10, K ≤ 5
320M ≤ 1
420Inga 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 · 3 · 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.

예제

예제 1

입력
3 4 0
출력
36

예제 2

입력
4 5 2
BE
BADC
출력
18

예제 3

입력
9 8 3
AC
CGD
BEFD
출력
2235978

출처 표기

출처: Programmeringsolympiaden 2020년 학교 예선 · 원문 페이지 · 이용 조건 CC BY-SA · LaTeX 원문을 화면용 글로 옮겼습니다(수식·표의 모양이 다를 수 있습니다). 내용은 고치지 않았습니다.

크리에이티브 커먼즈 저작자표시-동일조건변경허락.

문제 출처: 한국정보올림피아드(KOI) (CC BY-NC-SA 4.0) · International Olympiad in Informatics (IOI) (CC BY) · Centre for Education in Mathematics and Computing (CEMC), University of Waterloo (CC BY-NC 4.0) · Programmeringsolympiaden (CC BY-SA) · CSES Problem Set (Antti Laaksonen) (CC BY-NC-SA 4.0). 루미 알고리즘은 위 단체들과 관계없는 별도의 서비스이며, 자료는 원문 그대로 싣습니다. 문제마다 출처와 이용 조건을 따로 표기합니다.