Fişierul intrare/ieşire:aiacuxor.in, aiacuxor.outSursăGrigore Moisil 2017, 9
AutorMircea Popoveniuc, Razvan SalajanAdăugată degrigore.moisilGrigore Moisil grigore.moisil
Timp execuţie pe test0.5 secLimită de memorie65536 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Aiacuxor

Bulănel nu a fost atent la ora de informatică şi drept urmare a înţeles prost tema primită. Fiindcă nu e în stare să o facă, vă cere vouă ajutorul.
Bulănel are un şir V cu N elemente. Fie f(i,j)= suma xor a elementelor subsecvenţei determinate de poziţiile cuprinse între [i,j], i≤j ( V(i) xor V(i+1) xor … xor V(j) ). Bulănel e curios să afle care este suma xor a valorilor returnate de funcţia f pentru toate subsecvenţele din şirul V cu lungimea cuprinsă între [X, Y] (X≤Y). Deoarece e curios Bulănel vă pune Q astfel de întrebări.
Având în vedere că Bulănel stă prost cu cititul, veţi construi voi şirul V pe baza unui şir auxiliar S de lungime M, cu elemente numerotate de la 0 la M-1. Elementul de pe fiecare poziţie i, 0 ≤ i < N, din vectorul V va fi calculat cu următoarea formulă:
V[i] = (S[i / M] xor S[i mod M]) + i, unde x / y reprezintă câtul împărţirii lui x la y, x mod y reprezintă restul lui x la împărţirea cu y, 
şi x xor y reprezintă rezultatul operaţiei xor (sau exclusiv pe biţi) dintre x şi y.

De asemenea şi întrebările se generează în felul următor: ştiind prima intrebare X Y, următoarele perechi X Y se afla după procedeul:
X_nou = (X * A + Y * B) mod N + 1
Y_nou = (Y * C + (Z mod N) * D) mod N + 1, (unde Z reprezintă răspunsul ultimei întrebări iar A, B, C, D sunt nişte constante date în fişierul de intrare)
daca X_nou > Y_nou:
     interschimba X_nou, Y_nou_$
X = X_nou
Y = Y_nou

Cerinta

Cunoscând N, numărul de elemente din şirul V, Q numărul de întrebări şi şirul S cu ajutorul căruia vă veţi construi şirul V Bulănel vă roagă să îi răspundeţi corect la toate cele Q întrebări.

Date de intrare

Fişierul de intrare aiacuxor.in conţine pe prima linie un număr natural N, care reprezintă lungimea şirului V, urmat de Q, care reprezintă numarul de întrebări, şi M, lungimea şirului auxiliar S. Pe următoarea linie se află M numere, reprezentând şirul S cu elemente numerotate de la 0 la M-1. Pe a treia linie se afla X şi Y, care reprezintă lungimea minimă, respectiv lungimea maximă, ale secvenţelor luate în calcul pentru prima întrebare iar în continuare urmează în ordine A, B, C, D, constantele cu ajutorul cărora vă veţi construi următoarele întrebări, de la a doua până la a Q-a.

Date de ieşire

În fişierul de ieşire aiacuxor.out contine Q linii, fiecare conţinând răspunsul corespunzator celei de a i-a întrebare.

Restricţii

  • 1 ≤ X ≤ Y ≤ N ≤ 1000000
  • 1 ≤ Q ≤ 1000000
  • 1 ≤ M ≤ 1000, N ≤ M * M
  • Pentru 20 de puncte 1 ≤ N , Q ≤ 100
  • Pentru alte 20 de puncte 1 ≤ N ≤ 1000 si 1 ≤ Q ≤ 100
  • Pentru alte 15 de puncte 1 ≤ N ≤ 10000 si 1 ≤ Q ≤ 100
  • Elemente şirului V încap pe 32 de biti
  • 1 ≤ S[i] < 2^29
  • 0 ≤ A,B,C,D ≤ 10^3
  • O subsecvenţă este un subşir de elemente care apar pe poziţii consecutive în şirul iniţial
  • Operaţia xor reprezintă operaţia de disjuncţie exclusivă realizată pe biţii operanzilor. În Pascal, operatorul corespunzător este xor, iar în C/C++ acest operator este ^. De exemplu, 20 xor 14 = 26.
  • Modul de generare al şirului, respectiv a întrebărilor, se datorează doar faptului că Bulănel citeşte foarte greu.
  • Problema va fi evaluată pe teste în valoare de 90 de puncte
  • Se vor acorda 10 puncte din oficiu

Exemplu

aiacuxor.inaiacuxor.outexplicatie
4 4 4
10 8 10 8
1 1 9 8 5 3
4
5
0
1
Sirul V de lungime N = 4 : 0 3 2 5
Cele 4 intrebari sunt:
1 1
2 2
2 3
3 4
Vom explica în detaliu răspunsul pentru ultima întrebare:
Secvenţele din şirul V cu lungimea cuprinsă între [3, 4] sunt:
(0, 3, 2) (între poziţiile 0 şi 2);
(3, 2, 5) (între poziţiile 1 şi 3);
(0, 3, 2, 5) (între poziţiile 0 şi 3).
f(0, 2) = 0 xor 3 xor 2 = 1
f(1, 3) = 3 xor 2 xor 5 = 4
f(0, 3) = 0 xor 3 xor 2 xor 5 = 4
Răspunsul pentru ultima intrebare este: 1 xor 4 xor 4 = 1
10 10 4
2 8 9 1
6 9 9 6 2 9
28
5
23
5
22
22
23
11
0
0
Se obtine şirul V:
0 11 13 6 14 5 7 16 19 10
Se obţin întrebările:
6 9
1 9
4 4
1 6
6 8
3 5
8 9
6 7
4 7
5 9
Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?