Editing 1683 - xor1

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.
== Cerința ==
Se cere să se răspundă la q întrebări de forma “Pentru i și j date, să se determine numărul situat pe linia i coloana j a matricei”. Pentru a genera cele q întrebări vor fi cunoscute următoarele valori: i1,j1,a,b,m.
i1,j1 reprezintă valorile pentru prima întrebare. Următoarele întrebări ik, jk vor fi generate una din alta folosind următoarea regulă:
ik=(a∗ik−1+b) mod m
jk=(a∗jk−1+b) mod m
== Date de intrare ==
Fișierul de intrare xor1in.txt conține pe prima linie numerele naturale q,i1,j1,a,b,m separate prin câte un spaţiu.
== Date de ieșire == 
Fișierul de ieșire xor1out.txt va conține q linii. Pe linia k se va afișa elementul situat pe linia ik coloana jk a matricei.
== Restricții și precizări ==
*Pentru 10% dintre teste '''1 ≤ q ≤ 100, 1 ≤ m ≤ 100'''
*Pentru alte 10% dintre teste '''1 ≤ q ≤ 100000, 1 ≤ m ≤ 1000'''
*Pentru alte 30% dintre teste '''1 ≤ q ≤ 50, 1 ≤ m ≤ 30000'''
*Pentru alte 50% dintre teste '''1 ≤ q ≤ 100000, 1 ≤ m ≤ 108'''
*'''0≤i1,j1<m'''
*'''1 ≤ a,b ≤ 9'''
== Exemplul 1 ==
; xor1in.txt
: 4 2 3 1 1 5
; xor1out.txt
:2
:7
:0
:1
<br>
== Exemplul 2 ==
; xor1in.txt
: 5 2 3 1 1 5
; xor1.out.txt
:1
:1
:1
:1
:1
<br>
== Rezolvare == 
<syntaxhighlight lang="python" line>
#1683 - xor1
def generate_matrix_element(i, j, a, b, m):
    row = [(a * k + b) % m for k in range(j + 1)]
    return row

def main():
    # Deschideți fișierul xor1in.txt pentru citire
    with open("xor1in.txt", "r") as file:
        # Citiți valorile q, i1, j1, a, b, m din fișier
        q, i1, j1, a, b, m = map(int, file.readline().split())

    for _ in range(q):
        current_row = generate_matrix_element(i1, j1, a, b, m)
        result = current_row[j1]
        # Utilizați result într-un mod necunoscut sau salvați-l într-un loc
        print(result)
        i1 = (a * i1 + b) % m
        j1 = (a * j1 + b) % m

if __name__ == "__main__":
    main()
</syntaxhighlight>

== Explicatie ==
Avem q=4 întrebări.
Pentru i1=2, j1=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.