Fişierul intrare/ieşire:	divk.in, divk.out	Sursă	preONI 2006 Runda Finala
Autor	Filip Cristian Buruiana	Adăugată de
Timp execuţie pe test	0.1 sec	Limită de memorie	65536 kbytes
Scorul tău	N/A	Dificultate	1/5

Vezi solutiile trimise | Statistici

Divk

Fie un vector de N numere naturale nenule. Pentru tripletul (K, A, B) dat trebuie sa raspundem la intrebarea: cate subsecvente ale vectorului dat au lungimea cuprinsa intre A si B ( inclusiv ) si au suma elementelor divizibila cu K?

Cerinta

Sa se determine numarul subsecventelor cu proprietatea enuntata.

Date de Intrare

Prima linie a fisierului divk.in contine patru numere naturale N, K, A si B, separate prin cate un spatiu, avand semnificatia descrisa in enunt. Fiecare din urmatoarele N linii contine cate un numar natural nenul, elementele vectorului.

Date de Iesire

Prima linie a fisierului divk.out contine un numar natural T, numarul de subsecvente cu proprietatea ceruta.

Restrictii si precizari

• 1 < A < B < N ≤ 500 000
• 2 ≤ K ≤ 100 000
• Fiecare numar din cele N nu depaseste 10 000 000 ( 10 milioane )
• Prin subsecventa intelegem orice insiruire de termeni din vector care sunt pe pozitii consecutive

Exemplu

Explicatie

Subsecventele care pot fi alese sunt: , (4 1), (5 4 1) si (1 4).

Cum se trimit solutii?