Zgłaszanie | Wszystkie zgłoszenia | Najlepsze | Lista |
LETTERS5 - Listy i koperty 1 i pół |
Jaś nadal pracuje na poczcie. Jego szef wymyślił nowy problem podobny do tego, co za pierwszym razem. Znów napisano n listów i zaadresowano dla nich n kopert. Szefa interesuje tym razem to, na ile sposobów można włożyć listy do kopert tak, aby dokładnie k listów trafiło do właściwych kopert. Ponieważ ta szukana liczba może być bardzo duża, należy ją podać modulo p (gdzie p to pewna dana liczba pierwsza).
Wejście
Pierwsza linia zawiera dwie liczby całkowite: liczbę testów t (t≤20000) oraz liczbę pierwszą p (p<1000).
W kolejnych t liniach znajdują się po dwie liczby całkowite n i k. Pierwsza z nich to liczba wszystkich listów (i jednocześnie kopert), druga - liczba listów, które mają trafić do właściwych kopert. Zachodzi: 0≤k≤n≤2*1018.
Wyjście
Dla każdego przypadku testowego, w osobnej linii, jedna liczba całkowita, oznaczająca na ile sposobów (modulo p) można włożyć listy do kopert, zgodnie z życzeniem szefa.
Przykład
Wejście: 4 5 0 0 3 1 4 2 5 4 Wyjście: 1 3 1 0
Dodane przez: | Witold Długosz |
Data dodania: | 2012-04-09 |
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 |