== include(page="template/taskheader" task_id="xor3") ==
Poveste şi cerinţă...
Se consideră o matrice cu un număr infinit de linii şi coloane indexate începând cu $0$. Pe prima linie matricea conţine şirul numerelor naturale $(0, 1, 2, 3 ...)$. Pe fiecare linie începând cu linia a doua pe poziţia $j$ matricea conţine suma xor a elementelor situate pe linia anterioara de la poziţia $0$ până la poziţia $j$.
h2. Cerinta
Se cere să se răspundă la Q întrebări de forma “Pentru $i$ si $j$ date, să se determine numărul situat pe linia $i$ si coloana $j$ a matricei”. Pentru a genera cele întrebări vor fi cunoscute următoarele valori: $i{~1~}, j{~1~}, a, b, m$. Dintre acestea, i{~1~} si j{~1~} reprezintă valorile pentru prima întrebare. Următoarele întrebări vor fi generate una din alta folosind următoarea regulă:
* $i{~k~} = (a*i{~k-1~} + b) mod m$
* $j{~k~} = (a*j{~k-1~} + b) mod m$
h2. Date de intrare
Fişierul de intrare $xor3.in$ ...
Fişierul de intrare $xor3.in$ conţine pe prima linie numerele naturale $Q, i{~1~}, j{~1~}, a, b, m$ separate prin câte un spaţiu.
h2. Date de ieşire
În fişierul de ieşire $xor3.out$ ...
Fişierul de ieşire $xor3.out$ va conţine $Q$ linii. Pe linia $k$ se va afişa elementul situat pe linia $i{~k~}$ coloana $j{~k~}$ a matricei.
h2. Restricţii
* $... ≤ ... ≤ ...$
* Pentru $10%$ din teste, $1 ≤ Q ≤ 100$ si $1 ≤ m ≤ 100$.
* Pentru alte $10%$ din teste, $1 ≤ Q ≤ 100.000$ si $1 ≤ m ≤ 1000$.
* Pentru alte $30%$ din teste, $1 ≤ Q ≤ 50$ si $1 ≤ m ≤ 30.000$.
* Pentru restul de $50%$ din teste, $1 ≤ Q ≤ 100.000$ si $1 ≤ m ≤ 10^8^$.
* $0 ≤ i{~1~}, j{~1~} < m$.
* $1 ≤ a, b ≤ 9$.
h2. Exemplu
table(example). |_. xor3.in |_. xor3.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
...
table(example). |_. xor3.in |_. xor3.out |_. Explicatie |
| 4 2 3 1 1 5
| 2
7
0
1
| Avem q = 4 întrebări.
Pentru i{~1~} = 2, j{~1~} = 3, a = 1, b = 1, m = 5 se obţin întrebările: (2, 3), (3, 4), (4, 0), (0, 1).
Matricea este:
0 +**1**+ 2 3 4 5 6 ...
0 1 3 0 4 1 7 ...
0 1 2 +**2**+ 6 7 0 ...
0 1 3 1 +**7**+ 0 0 ...
+**0**+ 1 2 3 4 4 4 ...
.................
Se observă că pe poziţiile corespunzătoare
întrebărilor avem valorile 2, 7, 0 şi 1 |
== include(page="template/taskfooter" task_id="xor3") ==
