Livrare#10955

Livrare

1,5 secunde

256 de megabyți

Ușor

Problema:

Ai un șir de numere întregi, $A = [a_{1}, a_{2}, \dots, a_{n}]$ A = [a_1, a_2, \ldots, a_n], și un număr întreg $k$ . Trebuie să găsești numărul de subsecvențe ale șirului $A$ care au suma elementelor egală cu $k$ . O subsecvență a șirului $A$ este un șir care poate fi obținut prin eliminarea unor elemente (posibil niciunul) din $A$ , fără a schimba ordinea celorlalte elemente.

Intrare:

Prima linie conține două numere întregi $n$ și $k$ ( $1 \leq n \leq 1000$ 1 \leq n \leq 1000, $- 1 0^{9} \leq k \leq 1 0^{9}$ -10^9 \leq k \leq 10^9) — lungimea șirului și suma țintă.
A doua linie conține $n$ numere întregi $a_{1}, a_{2}, \dots, a_{n}$ a_1, a_2, \ldots, a_n ( $- 1 0^{9} \leq a_{i} \leq 1 0^{9}$ -10^9 \leq a_i \leq 10^9) — elementele șirului $A$ .

Ieșire:

Afișați un singur număr întreg — numărul de subsecvențe ale șirului $A$ a căror sumă este egală cu $k$ .

Exemple

Exemplul 1

Loading

A = [a_{1}, a_{2}, \dots, a_{n}]

1 \leq n \leq 1000

- 1 0^{9} \leq k \leq 1 0^{9}

a_{1}, a_{2}, \dots, a_{n}

- 1 0^{9} \leq a_{i} \leq 1 0^{9}