Rezolvare PBinfo #4233

Cerința

Se dă un șir a1, a2, …, an de numere întregi și un număr întreg S. Să se determine numărul secvențelor nevide care au suma egală cu S.

Date de intrare

Programul citește de la tastatură de pe prima linie numerele n, S, iar de pe a doua linie numerele separate prin spații a1, a2, …, an.

Date de ieșire

Programul va afișa pe ecran numărul numărul secvențelor nevide care au suma egală cu S.

Restricții și precizări

• 1 ≤ n ≤ 1.000.000
• -1000 ≤ ai ≤ 1000 pentru orice i=1..n
• -1.000.000.000 ≤ S ≤ 1.000.000.000
• O secvență nevidă este formată din unul sau mai multe elemente ale șirului aflate pe poziții consecutive.

Exemplu:

Intrare

13 -10
2 3 -11 1 -11 4 -8 10 -14 10 -5 4 -17

Ieșire

4

Explicație

Cele 4 secvențe de sumă S = -10 sunt:
-11, 1
1, -11
2, 3, -11, 1, -11, 4, -8, 10
-11, 4, -8, 10, -14, 10, -5, 4