Fişierul intrare/ieşire:	pensula.in, pensula.out	Sursă	Concurs de incalzire 2020
Autor	Alexandru Petrescu	Adăugată de	Bogdan Pop •Bodo171
Timp execuţie pe test	0.2 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Pensula

De la ultima oara cand se prefacea ca e un artist de mana a doua, Marcel si-a rafinat metodele. Acum are un arbore cu radacina, M culori cu indici de la 0 la M-1 si o pensula magica. De Q ori, isi va alege un nod si o culoare, va inmuia pensula in culoarea respectiva, si, dintr-o lovitura, va recolora in aceasta culoare toate nodurile de pe lantul de la nodul ales pana la radacina. La final, se intreaba, pentru fiecare nod in parte, care este gradul său de zapaceala. De fiecare data cand un nod care are culoarea de indice u este recolorat in culoarea v, gradul său de zapaceala creste cu u xor v (in limbaj C(++), folosim operatorul u ^ v).

Date de intrare

Desi solutia oficiala nu se foloseste de acest aspect, operatiile nu se vor afla explicit in input. Ele vor fi generate pseudo-aleator , dupa cum urmeaza sa explicam.

Fişierul de intrare pensula.in contine, pe prima linie, numarul N de noduri din arbore, numerele M si Q, si numarul C al carui scop e descris mai jos. Pe a doua linie se afla N numere, reprezentand tatal fiecarui nod. Daca tatal este 0, inseamna ca nodul respectiv este radacina. Initial, toate nodurile au culoarea cu indice 0. Cele Q perechi (nod, culoare) sunt generate asfel:

long long m = M;
unsigned int c = C;
for (int i = 0; i < Q; i++) {
    c = 5 * c + 1;
    int nod = i % N + 1;
    int culoare = (m * c) >> 32;
}

Date de ieşire

În fişierul de ieşire pensula.out se afla numarul ans, calculat dupa cum urmeaza. Daca in sirul res[i] retinem gradul de zapaceala al fiecarui nod i, putem obtine raspunsul astfel:

int ans = 0;
for (int i = 1; i <= N; i++)
    ans = (23LL * ans + res[i]) % 1000000007;

Restricţii

• 1 ≤ N ≤ 100.000
• 1 ≤ M ≤ 1.000.000.000
• 1 ≤ Q ≤ 700.000
• 1 ≤ C < 2³¹
• Pentru 50 de puncte, se garanteaza ca gradul fiecarui nod este maxim 2; cu alte cuvinte, arborele este o linie sau lant
• Pentru 30 de puncte din cele 50 descrise anterior, se garanteaza si ca radacina are gradul 1; cu alte cuvinte, radacina se afla intr-unul din capetele liniei sau lantului
• Pentru 20 de puncte, N ≤ 2.000 si Q ≤ 4.000 - o parte din puncte sunt comune cu cele descrise mai sus
• Pentru 60 de puncte, N ≤ 60.000 si Q ≤ 120.000 - idem

Exemplu

Explicaţie

res[1..9] = 17 51 26 73 7 4 0 19 101

Cum se trimit solutii?