Prologin
2024
Énoncé¶
Lors de sa petite marche matinale, Joseph Marchand tombe sur un étang plein de grenouilles. Ces grenouilles sont assez particulières : chacune possède un unique parent, aussi présent dans l'étang, à l'exception de l'unique plus ancienne des grenouilles, qui elle n'en a pas.
Elles lui disent, l'une après l'autre, qui sont leurs parents. Joseph note cela très précieusement dans son petit journal de voyage. Il se fait la remarque alors qu'il doit y avoir un sacré nombre de cousines dans l'étang !
Une grenouille est dite cousine d'une seconde d'ancienneté $p$, ou $p$-cousine, si leur plus jeune ancêtre commun est leur $p$-ancêtre. Par exemple des 1-cousines sont des sœurs.
Une grenouille est une p-ancêtre d'une autre si elles sont séparées par p degrés de parenté : une parente est une 1-ancêtre, une grand-parente est une 2-ancêtre, et ainsi de suite.
Joseph souhaite établir alors la liste des $p$-cousines pour chaque $p$ possible.
Aidez Joseph en lui donnant le nombre de couples (non ordonnés) de $p$-cousines pour chaque $p$ entre 1 et 10 (il n'y a pas plus de 11 générations de grenouilles dans l'étang).
Les grenouilles sont numérotées de 0 à $N - 1$, la grenouille 0 étant la plus ancienne.
Entrée¶
L'entrée comprendra plusieurs lignes :
- La première ligne contiendra un entier $N$, le nombre total de grenouille
- $N - 1$ lignes suivent, la i-ème d'entre elles donnera le numéro de la grenouille parente de la grenouille $i$.
Sortie¶
Vous afficherez 10 lignes, la i-ème ligne contiendra le nombre de couples de $i$-cousines.
Contraintes¶
- $1 \le N \le 500$
Contraintes de performance¶
- $1 \le N \le 100\ 000$