Permutacja
Limit pamięci: 32 MB
Multizbiorem nazywamy obiekt matematyczny podobny do zbioru,
w którym jednak ten sam element może występować wielokrotnie.
Podobnie jak w przypadku zbioru, także dla multizbioru wszystkie
elementy można ustawić w ciąg i to zazwyczaj na wiele sposobów;
każde takie ustawienie nazywamy permutacją multizbioru.
Dla przykładu, permutacjami multizbioru
są między innymi oraz .
Powiemy, że jedna permutacja danego multizbioru jest mniejsza
(w porządku leksykograficznym) od drugiej, jeżeli na pierwszej
pozycji, na której te permutacje się różnią, pierwsza z nich
zawiera element mniejszy niż druga.
Wszystkie permutacje danego multizbioru można ponumerować
(zaczynając od jedynki) w kolejności od najmniejszej do największej.
Zadanie
Napisz program, który:
-
wczyta ze standardowego wejścia opis permutacji pewnego multizbioru
oraz dodatnią liczbę ,
-
wyznaczy numer wczytanej permutacji w porządku leksykograficznym,
a dokładniej jego resztę z dzielenia przez ,
-
wypisze wynik na standardowe wyjście.
Wejście
Pierwszy wiersz wejścia zawiera dwie liczby całkowite oraz
(, ),
oddzielone pojedynczym odstępem.
Oznaczają one odpowiednio liczbę elementów multizbioru oraz ... liczbę .
Drugi wiersz wejścia zawiera dodatnich liczb całkowitych
(), pooddzielanych pojedynczymi odstępami
i oznaczających kolejne elementy danej permutacji multizbioru.
Wyjście
Pierwszy i jedyny wiersz wyjścia powinien zawierać jedną liczbę
całkowitą, oznaczającą resztę z dzielenia przez numeru
podanej permutacji w porządku leksykograficznym.
Przykład
Dla danych wejściowych:
4 1000
2 1 10 2
poprawną odpowiedzią jest:
5
Wszystkie permutacje mniejsze od zadanej to (w kolejności leksykograficznej):
,
,
oraz
.
Autor zadania: Jakub Radoszewski.