| Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
AL_26_06 - Alfabet |
Alfabet
Dany jest alfabet złożony z n różnych liter. Ciąg liter z tego alfabetu nazwiemy słowem, jeśli między dwiema takimi samymi literami nie ma innej pary takich samych liter. Ile jest słów nad tym alfabetem o maksymalnej długości?
Wejście
W pierwszym wierszu wejścia znajduje się liczba całkowita d (1 ≤ d ≤ 104) oznaczająca liczbę przypadków testowych. Dla każdego przypadku, w osobnym wierszu, znajduje się liczba całkowita n (1 ≤ n ≤ 106) oznaczająca długość alfabetu.
Wyjście
Dla każdego przypadku testowego należy wypisać resztę z dzielenia przez 109+9 liczby będącej odpowiedzią na zadane pytanie.
Przykład
Wejście
2
2
3
Wyjście
4
24
Dla alfabetu złożonego z dwóch liter otrzymujemy cztery słowa o maksymalnej długości: aaabbb, aababb, bbbaaa, bbabaa
| Dodane przez: | Mariusz Śliwiński |
| Data dodania: | 2015-12-01 |
| Limit czasu wykonania programu: | 1s |
| Limit długości kodu źródłowego | 50000B |
| Limit pamięci: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Języki programowania: | All except: ASM64 GOSU JS-MONKEY |
ukryj komentarze
|
2015-12-26 15:18:36 Marcin Kasprowicz
Rafał Kilar proszę o kontakt: fraktal@algorytm.edu.pl |
|
|
2015-12-26 14:08:02 Mariusz ¦liwiñski
Mamy święta, więc proszę bardzo :-) Dla n=4 wynikiem jest 192 |
|
|
2015-12-26 14:02:22 Sebastian Toton
Mogę prosić o odpowiedź dla n = 4? |
RSS