Fişierul intrare/ieşire:cia.in, cia.outSursăInfoOltenia 2018 - Clasele 9 - 10 Echipe
AutorBogdan IordacheAdăugată deinfoolteniaInfo-Oltenia 2018 infooltenia
Timp execuţie pe test4 secLimită de memorie262144 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

CIA

Pentagonul a primit un nou mesaj de la unul din agenţii săi secreţi. Mesajul este reprezentat de un şir de N numere naturale. Pentru a putea verifica autenticitatea mesajului, agenţii trebuie să ataşeze la mesaj o cheie de verificare, a cărei metodă de obţinere este cunoscută doar de către membrii agenţiei. Comisia InfoOltenia a reuşit să afle această metodă: având la dispoziţie 2 numere M şi K cunoscute, pentru fiecare subsecvenţă de K numere din şir se calculează restul împărţirii produsului lor la M, iar cheia de verificare va fi suma xor a acestor resturi.

Cerinţă

Cunoscându-se M, K şi şirul de numere pe care comisia vrea să îl trimită Pentagonului, determinaţi cheia de verificare corespunzătoare şirului de numere, care trebuie ataşată mesajului.

Date de intrare

Prima linie a fişierului cia.in va conţine numerele N, T, K şi M. A doua linie va conţine elementele unui şir A, de T numere naturale. A treia linie va conţine elementele unui şir B, de T numere naturale. Fie V şirul de N numere care trebuie transmis, pentru fiecare i (0 ≤ i ≤ N - 1) V[i] se va calcula după formula: V[i] = (A[i mod T] xor B[i div T]) mod M. Şirurile V, A, B sunt indexate de la 0, a mod b reprezintă restul împărţirii lui a la b, a div b reprezintă câtul împărţirii lui a la b, iar a xor b, suma xor a numerelor a şi b.

Date de ieşire

În fişierul cia.out afişaţi pe prima linie cheia de verificare corespunzătoare şirului dat.

Restricţii

  • T ≤ 70.000
  • 1 ≤ K ≤ N ≤ 107
  • 1 ≤ M < 230
  • Elementele şirurilor A şi B sunt numere naturale în intervalul [0,231).
  • pentru 5% din punctaj: 1 ≤ N*K ≤ 107
  • pentru alte 15% din punctaj 1 ≤ N ≤ 200.000, iar M este prim
  • pentru alte 15% din punctaj 1 ≤ M ≤ 107 , M este prim
  • pentru alte 25% din punctaj 1 ≤ N ≤ 200.000
  • prin subsecvenţă se înţelege un subşir de elemente plasate pe poziţii consecutive.
  • suma xor a P numere a 1, a 2, a 3 ... a P este egala cu a1 xor a2 xor a3 xor ... xor aP.

Exemplu

cia.incia.out
4 3 3 15
3 4 1
5 5 2
0

Explicaţie

Şirul ce trebuie transmis este (6, 1, 4, 6).
Avem 2 subsecvenţe de lungime 3. Ambele au produsul elementelor 24, deci ambele au restul împărţirii produsului elementelor la 15 egal cu 9.
Suma xor a numerelor 9 şi 9 este 9 xor 9 = 0.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?