const LN10 = ln(10); Epsilon = 1E-7; {Přesnost numerických chyb u floatových operací} type PVelkeCislo = ^TVelkeCislo; TVelkeCislo = object {Dlouhé celé kladné číslo} private Cifry:array of integer; procedure ZmenDelku(NovaDelka:integer); {V případě, že zkracujeme, zahazuje nejvyšší cifry} public constructor Nove; constructor Kopiruj(Vzor:PVelkeCislo); destructor Zrus; procedure Pricti(Co:PVelkeCislo); procedure Odecti(Co:PVelkeCislo); {Předpokládá, že výsledek bude kladný} procedure Vynasob(Cim:PVelkeCislo); procedure Posun(OKolik:integer); {Posune o příslušný počet míst vlevo či vpravo} {tj. vynásobí 10^OKolik, a případně zahodí desetinná místa} procedure NastavHodnotu(Kolik:integer); procedure Vypis; end; procedure TVelkeCislo.ZmenDelku(NovaDelka:integer); var StaraDelka:integer; i:integer; begin StaraDelka:=Length(Cifry); SetLength(Cifry,NovaDelka); for i:=StaraDelka to NovaDelka-1 do Cifry[i]:=0; {Nově vytvořené cifry nastaví na 0, aby se nezměnila hodnota čísla} end; constructor TVelkeCislo.Kopiruj(Vzor:PVelkeCislo); var i:integer; begin SetLength(Cifry,Length(Vzor^.Cifry)); for i:=0 to Length(Cifry)-1 do Cifry[i]:=Vzor^.Cifry[i]; end; constructor TVelkeCislo.Nove; begin ZmenDelku(0); end; destructor TVelkeCislo.Zrus; {Prázdný, freepascal se o dynamické pole v objektu stará sám, ale je třeba zavolat destruktor} begin end; procedure TVelkeCislo.Pricti(Co:PVelkeCislo); var i,Prenos,Soucet:integer; begin if Length(Co^.Cifry) > Length(Cifry) then ZmenDelku(Length(Co^.Cifry)); {Ať máme alespoň stejný počet cifer jako to, co přičítáme} Prenos:=0; for i:=0 to Length(Co^.Cifry)-1 do begin {Sčítání míst, kde mají cifry obě čísla} Soucet:=Co^.Cifry[i] + Cifry[i] + Prenos; Cifry[i]:=Soucet mod 10; Prenos:=Soucet div 10; end; if Prenos <> 0 then for i:=Length(Co^.Cifry) to Length(Cifry)-1 do begin {Pokud máme více cifer než přičítané číslo a zbývá přenos, přičítáme ho k cifrám "navíc"} Soucet:=Cifry[i] + Prenos; Cifry[i]:=Soucet mod 10; Prenos:=Soucet div 10; if Prenos=0 then break; end; if Prenos<>0 then begin {Přenos přesto zbyl, musíme tohle číslo o jednu cifru prodloužit} ZmenDelku(Length(Cifry)+1); Cifry[Length(Cifry)-1]:=Prenos; end; end; procedure TVelkeCislo.Odecti(Co:PVelkeCislo); var i,Prenos,Rozdil:integer; NejvyssiNenulova:integer; {Index cifry, nad kterou jsou již všechny nulové} begin if Length(Co^.Cifry) > Length(Cifry) then ZmenDelku(Length(Co^.Cifry)); {Srovnáme délku čísel ... i když tohle by se nemělo nikdy provést, předpokládáme kladný výsledek} Prenos:=0; NejvyssiNenulova:=0; for i:=0 to Length(Co^.Cifry)-1 do begin {Odečteme část, kde mají cifry obě čísla} Rozdil:=Cifry[i] - Co^.Cifry[i] - Prenos; if Rozdil<0 then begin Rozdil:=Rozdil + 10; Prenos:=1; end else Prenos:=0; Cifry[i]:=Rozdil; if Rozdil<>0 then NejvyssiNenulova:=i; end; for i:=Length(Co^.Cifry) to Length(Cifry)-1 do begin {Pokud máme více cifer než odčítané číslo a zbývá přenos, odečteme ho od cifer "navíc"} Cifry[i]:=Cifry[i] - Prenos; if Cifry[i]<0 then begin Cifry[i]:=Cifry[i] + 10; Prenos:=1; end else Prenos:=0; if Cifry[i]<>0 then NejvyssiNenulova:=i; end; ZmenDelku(NejvyssiNenulova+1); {V případě, že se nám některé cifry na začátku vynulovaly, upravíme délku čísla} end; procedure TVelkeCislo.Posun(OKolik:integer); {* 10^Okolik} var i,PuvodniDelka:integer; begin PuvodniDelka:=Length(Cifry); if OKolik>0 then begin {Posun doprava ... přidáváme nuly} ZmenDelku(PuvodniDelka+OKolik); for i:=PuvodniDelka-1 downto 0 do Cifry[i+OKolik]:=Cifry[i]; for i:=0 to OKolik-1 do Cifry[i]:=0; end else {Posun doleva ... sebereme několik posledních cifer} if PuvodniDelka+OKolik <= 0 then {Zbyde vůbec něco nenulového?} ZmenDelku(0) else begin for i:=-OKolik to PuvodniDelka-1 do Cifry[i+OKolik]:=Cifry[i]; ZmenDelku(PuvodniDelka+OKolik); end; end; procedure Nasob(C1,C2,Vysledek:PVelkeCislo); {Předpokládá, že C1 a C2 mají stejnou délku} {Rekurzivní násobění C1 a C2 - Karatsubův algoritmus, čas O(N^log_2(3))} {C1 = C1Horni * 10^M + C1Dolni , C2 = C2Horni * 10^M + C2Dolni} {C1*C2 = HorniSoucin * 10^(2*M) + StredniSoucin * 10^M + DolniSoucin} {HorniSoucin = C1Horni * C2Horni, DolniSoucin = C1Dolni * C2Dolni} {StredniSoucin (bude v poli Vysledek) = C1Horni * C2Dolni + C1Dolni * C2Horni =} { = (C1Horni + C1Dolni) * (C2Horni + C2Dolni) - HorniSoucin - DolniSoucin} var i,PulkaDelky,Soucin:integer; C1Horni,C2Horni,C1Dolni,C2Dolni:PVelkeCislo; DolniSoucin,HorniSoucin:PVelkeCislo; begin if Length(C1^.Cifry) = 0 then begin {Nula} Vysledek^.ZmenDelku(1); Vysledek^.Cifry[0]:=0; end else if Length(C1^.Cifry)=1 then begin {Jen cifra - vynásobíme "ručně"} Soucin:=C1^.Cifry[0]*C2^.Cifry[0]; if Soucin>9 then begin {Je výsledek jedno, či dvouciferný?} Vysledek^.ZmenDelku(2); Vysledek^.Cifry[0]:=Soucin mod 10; Vysledek^.Cifry[1]:=Soucin div 10; end else begin Vysledek^.ZmenDelku(1); Vysledek^.Cifry[0]:=Soucin; end; end else begin {Nyní rekurzivní část} PulkaDelky:=Length(C1^.Cifry) div 2; new(C1Horni,Nove); {Alokace prostoru pro pomocná čísla} new(C2Horni,Nove); new(C1Dolni,Nove); new(C2Dolni,Nove); new(DolniSoucin,Nove); new(HorniSoucin,Nove); C1Horni^.ZmenDelku(Length(C1^.Cifry)-PulkaDelky); {nyní rozdělíme C1 a C2 na poloviny} C2Horni^.ZmenDelku(Length(C1^.Cifry)-PulkaDelky); for i:=PulkaDelky to Length(C1^.Cifry)-1 do begin C1Horni^.Cifry[i-PulkaDelky]:=C1^.Cifry[i]; C2Horni^.Cifry[i-PulkaDelky]:=C2^.Cifry[i]; end; C1Dolni^.ZmenDelku(PulkaDelky); C2Dolni^.ZmenDelku(PulkaDelky); for i:=0 to PulkaDelky-1 do begin C1Dolni^.Cifry[i]:=C1^.Cifry[i]; C2Dolni^.Cifry[i]:=C2^.Cifry[i]; end; Nasob(C1Dolni,C2Dolni,DolniSoucin); {Ty rekurzivně vynásobíme} Nasob(C1Horni,C2Horni,HorniSoucin); C1Horni^.Pricti(C1Dolni); {A nyní spočteme střední součin - viz. úvod procedury} C2Horni^.Pricti(C2Dolni); Nasob(C1Horni,C2Horni,Vysledek); Vysledek^.Odecti(DolniSoucin); Vysledek^.Odecti(HorniSoucin); Vysledek^.Posun(PulkaDelky); {Posuneme součiny o příslušný počet míst} HorniSoucin^.Posun(2*PulkaDelky); Vysledek^.Pricti(DolniSoucin); {A posčítáme výsledky} Vysledek^.Pricti(HorniSoucin); dispose(C1Horni,Zrus); {Uvolnění pomocných čísel} dispose(C2Horni,Zrus); dispose(C1Dolni,Zrus); dispose(C2Dolni,Zrus); dispose(DolniSoucin,Zrus); dispose(HorniSoucin,Zrus); end; end; procedure TVelkeCislo.Vynasob(Cim:PVelkeCislo); {Srovná délky čísel a pak zavolá rekurzivní Karatsubovo násobení} var Vysledek,CimNasobime:PVelkeCislo; i:integer; begin new(Vysledek,Nove); {Pomocné číslo, kam se uloží výsledek} {Dalo by se obejít bez něj, je tu ale pro přehlednost} if Length(Cim^.Cifry) < Length(Cifry) then begin {Pokud je násobící číslo krátké, založíme kopii a upravíme její délku, aby odpovídala} new(CimNasobime,Kopiruj(Cim)); CimNasobime^.ZmenDelku(Length(Cifry)); end else begin {A pokud je krátké tohle číslo, přidáme cifry} CimNasobime:=Cim; ZmenDelku(Length(Cim^.Cifry)); end; Nasob(@Self,CimNasobime,Vysledek); {Rekurzivní vynásobení} SetLength(Cifry,Length(Vysledek^.Cifry)); {A výsledek okopírujeme z pomocného čísla sem} for i:=0 to Length(Cifry)-1 do Cifry[i]:=Vysledek^.Cifry[i]; if CimNasobime<>Cim then dispose(CimNasobime,Zrus); {Uvolnění všeho, co bylo alokováno navíc} dispose(Vysledek,Zrus); end; procedure TVelkeCislo.Vypis; {Vypíše číslo} var i:integer; begin if Length(Cifry)=0 then write(0) else begin for i:=Length(Cifry)-1 downto 0 do if Cifry[i]<>0 then break; while i>=0 do begin write(Cifry[i]); dec(i); end; end; end; procedure TVelkeCislo.NastavHodnotu(Kolik:integer); var i:integer; MinCifer:integer; begin if Kolik<0 then Kolik:=0; if Kolik=0 then MinCifer:=1 else MinCifer:=floor( ln(Kolik) / LN10 + Epsilon) + 1; {Zjistíme, kolik bude mít výsledek cifer.} {Epsilon je zde pro možnost, že zaokroouhlovací chyba bude menší než nula.} if Length(Cifry) < MinCifer then ZmenDelku(MinCifer); {Zajištění dostatku místa} for i:=0 to Length(Cifry)-1 do begin {A nastavení jednotlivých cifer} Cifry[i]:=Kolik mod 10; Kolik:=Kolik div 10; end; end; var n:integer; VelkySef:integer; {Nadřízený všech uvažovaných zaměstnanců} Podrizeni:array of integer; {První podřizený daného pracovníka, -1 pokud neexistuje} Spolupracovnici:array of integer; {Další podřízený stejného šéfa ... -1 pokud byl tenhle poslední} PocetSkupin:PVelkeCislo; {Kolika způsoby lze zaměstnance rozdělit} PocetPodstromu:PVelkecislo; Jednicka:PVelkeCislo; {1 ... jen zapsaná jako dlouhé číslo, bude se vyskytovat několikrát} PomocnaCisla:array of PVelkeCislo; procedure Nacti; var Sef:integer; i:integer; begin readln(n); SetLength(Podrizeni,n+1); for i:=1 to n do Podrizeni[i]:=-1; SetLength(Spolupracovnici,n+1); for i:=1 to n do begin readln(Sef); if Sef=-1 then begin {Postupně přidáváme zaměstanance do seznamu podřízených} Spolupracovnici[i]:=-1; VelkySef:=i; end else begin Spolupracovnici[i]:=Podrizeni[Sef]; Podrizeni[Sef]:=i; end; end; end; procedure Rekurze(KdeJsem:integer;Hloubka:Integer;PocetPodstromu:PVelkeCislo); var Podstromy:integer; PocetPodstromuPodrizeneho:PVelkeCislo; begin if Length(PomocnaCisla)=Hloubka then begin {Máme dost pomocných čísel?} {Hloubka vzrůstá o 1, takže případ Length < Hloubka nemůze nastat} SetLength(PomocnaCisla,Hloubka+1); new(PomocnaCisla[Hloubka],Nove); end; PocetPodstromuPodrizeneho:=PomocnaCisla[Hloubka]; PocetPodstromu^.NastavHodnotu(1); Podstromy:=Podrizeni[KdeJsem]; while Podstromy <> -1 do begin {Projdeme všechny podřízené a podíváme se, kolika způsoby můžeme vytvořit podskupinku} Rekurze(Podstromy,Hloubka+1,PocetPodstromuPodrizeneho); PocetPodstromuPodrizeneho^.Pricti(Jednicka); PocetPodstromu^.Vynasob(PocetPodstromuPodrizeneho); Podstromy:=Spolupracovnici[Podstromy]; end; PocetSkupin^.Pricti(PocetPodstromu); {Nakonec přičteme počet skupin, kde já jsem šéf, k celkovému počtu možností} end; begin Nacti; {Načtení vstupu} new(PocetSkupin,Nove); {Inicializace proměnných} new(PocetPodstromu,Nove); new(Jednicka,Nove); PocetSkupin^.NastavHodnotu(0); Jednicka^.NastavHodnotu(1); Rekurze(VelkySef,0,PocetPodstromu); {Vlastní výpočet} PocetSkupin^.Vypis; {Výpis výsledku} for n:=0 to Length(PomocnaCisla)-1 do dispose(PomocnaCisla[n],Zrus); {A uklizení paměti} dispose(PocetSkupin,Zrus); dispose(PocetPodstromu,Zrus); end.