== include(page="template/taskheader" task_id="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.
h2. 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.
Poveste şi cerinţă...
h2. 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$.
Fişierul de intrare $cia.in$ ...
h2. Date de ieşire
În fişierul $cia.out$ afişaţi pe prima linie cheia de verificare corespunzătoare şirului dat.
În fişierul de ieşire $cia.out$ ...
h2. Restricţii
* $T ≤ 70.000$
* $1 ≤ K ≤ N ≤ 10^7^$
* $1 ≤ M < 2^30^$
* Elementele şirurilor $A$ şi $B$ sunt numere naturale în intervalul $[0,2^31^)$.
* pentru $5%$ din punctaj: $1 ≤ N*K ≤ 10^7^$
* pentru alte $15%$ din punctaj $1 ≤ N ≤ 200.000$, iar $M$ este prim
* pentru alte $15%$ din punctaj $1 ≤ M ≤ 10^7^$ , $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 $a{~1~} xor a{~2~} xor a{~3~} xor ... xor a{~P~}.$
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. cia.in |_. cia.out |
| 4 3 3 15
3 4 1
5 5 2
| 0
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. 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$.
...
== include(page="template/taskfooter" task_id="cia") ==
== include(page="template/taskfooter" task_id="cia") ==
