Fişierul intrare/ieşire:	sandwich.in, sandwich.out	Sursă	Junior Challenge 2025
Autor	Muresan Luca Valentin	Adăugată de	Vlad Tutunaru •vlad2009
Timp execuţie pe test	0.7 sec	Limită de memorie	262144 kbytes
Scorul tău	N/A	Dificultate	N/A

Vezi solutiile trimise | Statistici

Sandwich

În Tărâmul Ooo, Jake vrea să pregătească sandwichul magic perfect. Pe o masă sunt aliniate N ingrediente numerotate de la 1 la N, iar ingredientul i are o valoare de „gust” a_i.

Pentru orice subsecvenţă de ingrediente a_l a_l+1 ... a_r, Jake poate alege un subşir de poziţii strict crescător (eventual gol) astfel încât să nu existe două poziţii adiacente alese. Gustul total acelui subşir este: a_i1 + a_i2 + ... + a_ik, cu l ≤ i₁ < i₂ < ... < i_k ≤ r şi i_j + 1 < i_j+1 pentru orice 1 ≤ j < k.

Definim = gustul total maxim posibil pentru un astfel de subşir.

Jake vrea să ştie suma celor mai gustoase sandwichuri pe care le poate face, dacă ia în calcul toate subsecvenţele posibile ale mesei. Cu alte cuvinte, calculaţi:

Date de intrare

Fişierul de intrare sandwich.in conţine numerele N, x, y, z şi a₁. Şirul a este codificat astfel:

a_i = (a_i-1 * x + y) % z pentru orice 2 ≤ i ≤ N

Date de ieşire

În fişierul de ieşire sandwich.out afişaţi valoarea lui S modulo 10⁹ + 7.

Restricţii

• 1 ≤ N ≤ 5 000 000
• 1 ≤ x, y ≤ 1 000 000 000
• 0 ≤ a₁ < z ≤ 1 000 000 000

Exemplu

Explicaţie

a = [5, 4, 1, 4]

f(a[1..1]) = 5
f(a[1..2]) = 5
f(a[1..3]) = 6
f(a[1..4]) = 9
f(a[2..2]) = 4
f(a[2..3]) = 4
f(a[2..4]) = 8
f(a[3..3]) = 1
f(a[3..4]) = 4
f(a[4..4]) = 4

S = 50

Cum se trimit solutii?