Heaps saymaq#5738
Bizə köklü bir ağac verilib və bu ağacda n təpə var. Təpələr 1, 2, ..., n nömrələri ilə etiketlənməlidir. Hər etiket unikal olmalı və yığın şərtinə uyğun gəlməlidir; yəni, hər hansı bir təpənin etiketi onun valideyninin etiketindən kiçik olmalıdır. Belə etiketləmələrin neçə fərqli üsulu mövcuddur? Bu say çox böyük ola biləcəyi üçün yalnız onun m modulu ilə qalıqını hesablayın.
Giriş bir neçə ağac təsvirindən ibarətdir. İlk sətir, ağacların sayını göstərən t (t ≤ 250) ədədini ehtiva edir. Hər bir ağacın təsviri, ağacın ölçüsünü n (1 ≤ n ≤ 500000) və bir tam ədəd m (2 ≤ m ≤ 10^9) göstərən bir sətirlə başlayır. Sonra n-1 sətir gəlir, burada i-ci sətir i+1-ci təpənin valideyninin nömrəsini p(i+1) göstərir (1 ≤ p(i+1) ≤ i). Hər bir ağacda 1 nömrəli təpə kök olacaq, buna görə onun valideyni göstərilməyəcək. Girişin ümumi ölçüsü 50MB-dan çox olmayacaq.
Hər bir ağac üçün, onun etibarlı etiketləmələrinin sayını verilmiş m modulu ilə çıxarın.
Nümunə üçün izah: Son nümunə test halında 8 mümkün etiketləmə aşağıdakı kimidir:
Nümunə 1