Diferente pentru problema/meow intre reviziile #4 si #8

Nu exista diferente intre titluri.

Diferente intre continut:

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:
Meow2 ar vrea să ştie după fiecare schimbare de câte ori apare şirul $1, 2, ..., L$ “î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 10^9^ + 7$.
h2. 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$.
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.
h2. Restricţii
* $... &le; ... &le; ...$
* $1 ≤ N ≤ 100 000$
* $1 ≤ L ≤ N$
* $0 ≤ F[i] < i$, pentru orice $i$
* $1 ≤ P[i], S[i] ≤ L$, pentru orice $i$
* $1 ≤ Q ≤ 200 000$
* Pentru $20$ de puncte: $N ≤ 200, L ≤ 30, Q ≤ 400$
* Pentru $50$ de puncte: $N ≤ 5 000, L ≤ 300, Q ≤ 5 000$
h2. Exemplu
table(example). |_. meow.in |_. meow.out |
| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.
|6 2 6
0 1 0 3 0
1 2 1 2 1 2
2
1
2
1
2
1
|29
|
h3. Explicaţie
...
În arborele iniţial, şirul $S$ apare de $3$ ori, dar după prima operaţie va apărea de $0$ ori, după a doua operaţie tot de $0$ ori, după a treia operaţie o dată, după a patra operaţie o dată, după a cincea operaţie de $2$ ori, dupa a saşea operaţie de $2$ ori.
Răspunsul este $1 * 0 + 2 * 0 + 3 * 1 + 4 * 1 + 5 * 2 + 6 * 2 = 29$
== include(page="template/taskfooter" task_id="meow") ==

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.