| Fişierul intrare/ieşire: | arbnr.in, arbnr.out | Sursă | Lot Iasi 2008, Baraj 6 |
| Autor | Emilian Miron | Adăugată de |  Adrian Diaconu •DITzoneC |
| Timp execuţie pe test | 0.275 sec | Limită de memorie | 20480 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Arbnr
Un arbore cu radacina este format dintr-o multime de noduri, dintre care un nod special denumit radacina. Fiecare nod are precizata o lista ordonata de noduri fiu, iar fiecare nod diferit de radacina este fiul al exact unui alt nod denumit parinte. Radacina nu are parinte. Subarborele unui nod X este un arbore cu radacina obtinut eliminand orice nod care nu este fiu direct sau indirect al nodului X si considerand nodul X radacina. Fie doi arbori cu radacina A, B cu radacinile rA si respectiv rB. Fie a1a2a3...ak lista ordonata a fiilor lui rA, b1b2b3...bp lista ordonata a fiilor lui rB. Spunem ca arborii A, B sunt egali daca p=k si pentru orice 1 ≤ i ≤ k subarborii cu radacinile ai si bi sunt egali. Spunem ca arborele A apare in arborele B daca exista un nod nB din B astfel incat subarborele cu radacina nB este egal cu arborele A.
Gigel are o afacere cu o multime de T arbori cu radacina (denumiti model) A1, A2, ..., AT. Gigel vinde numai arbori cu radacina avand N noduri in care nu apar nici unul dintre arborii model.
Cerinta
Scrieti un program care sa calculeze cati arbori cu radacina cu N noduri distincti poate vinde Gigel.
Date de intrare
Fisierul de intrare arbnr.in contine pe prima linie numerele naturale N si T reprezentand numarul de noduri din arborii vanduti de Gigel si respectiv numarul de arbori model. In continuare urmeaza T blocuri de date, fiecare bloc reprezentand descrierea unui arbore model. Blocul care descrie un arbore model contine pe prima linie un numar natural M reprezentand numarul de noduri din arbore. Pe cea de a doua linie sunt scrise M-1 numere naturale separate prin spatiu. Al i-lea numar de pe linie este nodul parinte al nodului i+1 (1 ≤ i ≤ M-1). Radacina este nodul cu numarul 1. Ordinea fiilor este considerata ordinea crescatoare a numerelor lor de ordine.
Date de iesire
Fisierul arbnr.out va contine o singura linie pe care va fi scris un numar natural reprezentand numarul de arbori cu radacina distincti cu N noduri in care nu apare nici unul dintre arborii model modulo 9907.
Restricţii
- 1 ≤ N ≤ 10.000
- 0 ≤ T ≤ 40
- 2 ≤ M ≤ 10.000
- 30% din punctaj se acorda pentru N,M ≤ 100 si T ≤ 10
- 65% din punctaj se acorda pentru M ≤ 500
Exemplu
| arbnr.in | arbnr.out |
|---|---|
| 4 2 3 1 2 3 1 1 | 3 |
