Fişierul intrare/ieşire:	expected2.in, expected2.out	Sursă	Tuymaada 2021
Autor	Alexandru Petrescu	Adăugată de	Alexandru Petrescu •alexpetrescu
Timp execuţie pe test	0.65 sec	Limită de memorie	524288 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Expected Xor

Se da un numar intreg pozitiv M si un sir de N numere intregi pozitive A_i, cu proprietatea ca (A_i, M) = 1 (adica cel mai mare divizor comun al numerelor A_i si M este 1). Gasiti valoarea medie asteptata a lui B₁ xor B₂ xor ... xor B_N, unde fiecare B_i este o un numar intreg aleatoar cu proprietatea ca 0 ≤ B_i < A_i. Se poate demonstra ca raspunsul este rational. El este cerut modulo M, dupa cum este descris mai jos.

Date de intrare

Fişierul de intrare expected2.in contine, pe prima linie, numerele M si N despartite prin cate un spatiu. Pe urmatoarea linie se afla N numere despartite prin cate un spatiu, reprezentand sirul A.

Date de ieşire

În fişierul de ieşire expected2.out se afla pe prima linie un numar natural X < M. Daca raspunsul este un numar rational U / V, atunci X are proprietatea X * V ≡ U (mod M).

Restricţii

• 1 ≤ N ≤ 50.000
• 2 ≤ M ≤ 10⁹+7
• 1 ≤ A_i ≤ 2⁶²
• Pentru 20 de puncte, N ≤ 5, M = 11, A_i < 2³
• Pentru alte 20 de puncte, N ≤ 100, M = 997, A_i ≤ 2⁵
• Pentru alte 20 de puncte, M = 10⁹+7
• Pentru alte 20 de puncte, N ≤ 1.000, M ≤ 10³, A_i < 2³⁰

Exemplu

Explicaţie

• In primul exemplu, raspunsul este 9 / 2 iar 10 * 2 = 20 ≡ 9 (modulo 11)
• In al doilea exemplu, raspunsul este 274 / 63 iar 8 * 63 = 504 ≡ 4 (modulo 10) ≡ 274

Cum se trimit solutii?