Divisible por i

Points: 100 (partial)

Time limit: 2.0s

Memory limit: 1G

Authors:

FrankHG, Alain_David

Problem type

Allowed languages

C, C++, Go, Java, Pascal, Python, VB

Dada una secuencia $A$ $A$ de $N$ $N$ números. Encuentre la cantidad de maneras de separar $A$ $A$ en algún número de subsecuencias contiguas no vacías $B_1, B_2,...,B_k$ $B_{1}, B_{2}, . . ., B_{k}$ tal que se cumpla la siguiente condición:

Para cada $i$ $i$ $(1 \leq i \leq k)$ $(1 \leq i \leq k)$ , la suma de los elementos en $B_i$ $B_{i}$ es divisible por $i$ $i$ .

Ya que dicha cantidad puede ser enorme, exprésela módulo $(10^9 + 7)$ $(10^{9} + 7)$ .

Constantes

$(1 \leq n \leq 3000)$ $(1 \leq n \leq 3000)$
$(1 \leq A_i \leq 10^{15})$ $(1 \leq A_{i} \leq 10^{15})$
Todos los valores de la entrada son enteros

Entrada

La entrada se dará en el siguiente formato:

$N$ $N$
$A_1$ $A_{1}$ $A_2$ $A_{2}$ $...$ $. . .$ $A_N$ $A_{N}$

Salida

Imprima la cantidad de formas de separar la secuencia de tal manera que se cumpla la condición antes descrita, módulo $(10^9 + 7)$ $(10^{9} + 7)$ .

Ejemplo #1 de Entrada

Copy

4
1 2 3 4

Ejemplo #1 de Salida

Copy

Tenemos tres maneras de separar la secuencia:

$(1),(2),(3),(4)$ $(1), (2), (3), (4)$
$(1,2,3),(4)$ $(1, 2, 3), (4)$
$(1,2,3,4)$ $(1, 2, 3, 4)$

Ejemplo #2 de Entrada

Copy

5
8 6 3 3 3

Ejemplo #2 de Salida

Copy

Ejemplo #3 de Entrada

Copy

10
791754273866483 706434917156797 714489398264550 918142301070506 559125109706263 694445720452148 648739025948445 869006293795825 718343486637033 934236559762733

Ejemplo #3 de Salida

Copy

Puede que los valores de la entrada no entren en un entero de $32$ $32$ -bit.

Comments

0

JoJo_Cubano_13 commented on Jan. 1, 2024, 9:39 p.m.

En definitiva un problema muy bonito. <3