Fişierul intrare/ieşire:arbnr.in, arbnr.outSursăLot Iasi 2008, Baraj 6
AutorEmilian MironAdăugată deDITzoneCAdrian Diaconu DITzoneC
Timp execuţie pe test0.55 secLimită de memorie20480 kbytes
Scorul tăuN/ADificultateN/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.inarbnr.out
4 2
3
1 2
3
1 1
3
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content