Runda 7 [Hard] - Kosmiczna komórka

17.01.2011 - Damian Rusak
TrudnośćTrudność

 

Zadanie tygodnia

Runda 7; kategoria Hard

Limit czasowy: 2s; Limit pamięciowy: 32MB


Kosmiczna komórka

Na planecie X od niepamiętnych lat korzysta się z telefonów komórkowych. Taki telefon przypomina nasze ziemskie telefony, z tą różnicą, że mieszkańcy planety X korzystają z innego zestawu cyfr, służącego do tworzenia numerów. Alfabet ten ma dokładnie $ N*M $ symboli, które zapisane są na klawiaturze telefonu w tabelce rozmiaru $ N $ X $ M $

Kosmici są bardzo wybredni i wymagają od numerów telefonów, aby były estetyczne. Numer estetyczny to taki numer, który może zaczynać się od dowolnej cyfry, jednak jego kolejne cyfry muszą być różne i sąsiadować ze sobą na klawiaturze telefonu (druga z pierwszą, trzecia z drugą, itd.) Powiemy, że dwie cyfry sąsiadują ze sobą, jeśli klawisze, na których są zapisane, mają wspólną krawędź (Na przykład na polskiej klawiaturze sąsiadują ze sobą 1 i 2 albo 1 i 4, ale 1 i 5 pomimo wspólnego rogu nie sąsiadują ze sobą).

Sieć komórkowa Y, która obsługuje znaczną część planety X planuje przydzielić swoim abonentom estetyczne numery długości $ k $. Jej pracownicy zastanawiają się, jak wiele może ich być. Aby to obliczyć, pewnej bezgwiezdnej nocy porwano Ciebie w strumieniu niebieskiego światła na statek kosmiczny i przetransportowano na planetę X. Czy uda Ci się pomóc kosmitom?

Wejście:

Pierwsza linia wejścia zawiera dwie liczby całkowite $ N $ oraz $ M $ - rozmiary klawiatury telefonu. ($ 1 \leq N, M \leq 10 $). W kolejnej linii znajduje się liczba $ k $ ($ 1 \leq k \leq 10^{9} $) - długość numerów.

Wyjście:

Jedyna linia wyjścia powinna zawierać jedną liczbę - liczbę możliwych do utworzenia estetycznych numerów, modulo $ 10^{9} + 7 $.

Przykład:

Wejście:

2 2
3

Wyjście:

16

Wytłumaczenie:  gdyby oznaczyć klawisze w pierwszym wierszu jako AB a w drugim jako CD, to można utworzyć jedynie następujące estetyczne numery:

ABA, ACA, ABD, ACD, BAB, BDB, BAC, BDC, CAC, CDC, CAB, CDB, DBD, DCD, DBA, DCA

 

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
PozycjaImię i nazwiskoWynikCzasKosmiczna komórka
1Maciej Kisiel1005:28:4510
2Piotr Bejda1006:27:0710
3Krzysztof Pszeniczny1006:56:5310
4Kamil Dębowski1031:35:0110
5Bartosz Tarnawski10123:43:2910
6Bartek Dudek10145:22:3510
7Przemysław Derengowski10155:51:4610
8Wojciech Staszkiewicz10434:52:5810
9Damian Straszak10773:41:2510
10Witold Długosz101439:32:0510
11Piotr Żurkowski222:06:442
12Mateusz Wasylkiewicz1127:33:371
3.8
Twoja ocena: Brak Ocena: 3.8 (5 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com