Revizia anterioară Revizia următoare
| Fişierul intrare/ieşire: | meow.in, meow.out | Sursă | Lot 2017 Baraj 2 |
| Autor | Alexandru Velea | Adăugată de |  Eugenie Daniel Posdarascu •eudanip |
| Timp execuţie pe test | 0.25 sec | Limită de memorie | 262144 kbytes |
| Scorul tău | N/A | Dificultate | N/A |
Vezi solutiile trimise | Statistici
Meow
În clubul de info a apărut un nou pokemon, Meow2. Fiind pasionat de copaci, Meow2 are un arbore cu rădăcină de N noduri, numerotate de la 0 la N-1. Nodul 0 este rădăcina arborelui şi, pentru orice nod diferit de 0, părintele lui are un indice strict mai mic decât el. Fiecare nod i are iniţial asociat un număr natural S[i] între 1 şi L.
Meow2 ar vrea să ştie de câte ori apare şirul 1, 2, …, L ca subşir “în jos” pe arborele iniţial. Formal, e interesat câte şiruri A0, A1, ... AL-1 există astfel încât fiecare nod Ai să aibă asociată valoarea i+1 şi, pentru fiecare 0 ≤ i < L-1, nodul Ai să fie strămoş (nu neapărat direct) al nodului Ai+1.
Fiind un pokemon în continuă evoluţie, Meow2 schimbă progresiv arborele iniţial. Mai exact, acesta are un şir magic de schimbări, P, de lungime Q, la pasul 0 ≤ i < Q schimbând numărul asociat nodului i%N în P[i], 1 ≤ P[i] ≤ L. Schimbarea de la pasul i va rămâne valabilă şi pentru paşii următori.
Meow2 ar vrea să ştie după fiecare schimbare de câte ori apare şirul S “în jos” pe arborele iniţial. Dacă notăm cu ans[ i ] răspunsul după a i-a schimbare, trebuie afişată suma:
O = (1 * ans[ 0 ] + 2 * ans[ 1 ] + … + q * ans[ q–1 ]) mod 109 + 7.
Date de intrare
Fişierul de intrare meow.in conţine pe prima linie trei numere naturale separate prin câte un spaţiu, N, L şi Q, cu semnificaţiile din enunţ.
Următoarea linie conţine şirul F de N–1 numere, numărul F[ i ] reprezentând tatăl nodului i.
A 3-a linie conţine şirul S de lungime N, reprezentând valorile iniţiale ale nodurilor din arbore.
Apoi urmează Q linii ce formează şirul P, reprezentând schimbările pe care le face Meow2 asupra arborelui în modul prezentat în enunţ, în ordine.
Date de ieşire
Fişierul meow.out va conţine suma O cerută modulo 109+7.
Restricţii
- ... ≤ ... ≤ ...
Exemplu
| meow.in | meow.out |
|---|---|
| This is some text written on multiple lines. | This is another text written on multiple lines. |
Explicaţie
...
