Soy ağacı#2851
İranın ad günündə çoxlu qohum vardI, buna görə də hamısını tanımaq çətin idi. Ümumi vəziyyəti anlamaq üçün soy ağacı qurmaq fikri yarandı. Lakin qarışıqlıq səbəbindən ağac ikili olmadı, amma zirvələrin sayı məntiqli idi — 2^k-1.
— Burada nəsə düzgün deyil. — Doğrudan? — Təkrar-təkrar yoxlamağı təklif edirəm. — Necə? — Ağacı əlaqəli hissələrə bölək, hər biri 2^i zirvədən ibarət olsun, hər kəs də öz hissəsini yoxlasın. — Niyə məhz belə? — Bilmirəm, iki üstü qüvvətləri xoşlayıram sadəcə. Ümumilikdə də dəqiq lazım olan qədər edəcək. Amma kiçik bir problem var: bunu etmək üçün çoxlu yol var. — Bəli, Sudoku və universitet gündəliklərini xatırladım. Bu dəfə neçə yol var? — Yaddaşın əladır. Mənə bir neçə dəqiqə ver, fikirləşim. — Buyur.
Birinci sətirdə bir tam ədəd verilir — N=2^k-1, ağacdakı zirvələrin sayı (1 \leq k \leq 12). Sonra gələn sətirdə N-1 tam ədəd verilir. a_i tam ədədi (1 \leq a_i < i+1) göstərir ki, i+1 və a_i zirvələri arasında kənar var. Zirvələr 1-dən başlayaraq nömrələnir.
Bir tam ədəd çap edin — ağacı dəqiq olaraq k əlaqəli bloklara bölmək üsullarının sayı; blokların ölçüləri isə müvafiq olaraq 1, 2, 4, ..., 2^k-1 olmalıdır. Hər bir zirvə yalnız bir bloka daxil olmalıdır.
Nümunə 1