Voluntarios P59328


Statement
 

pdf   zip

html

Hay que seleccionar unos cuantos aprendices de mago del Colegio Hogwarts de Magia y Hechicería para ir a luchar contra aquél que no puede ser nombrado. Hay n cursos distintos, y cada uno de ellos está dividido en exactamente k grupos (G1, G2, …, Gk). Cada uno de los nk grupos ha seleccionado a un único “voluntario” entre sus integrantes. La responsabilidad del director Dumbledore es escoger a t≤ nk de estos voluntarios, con las siguientes restricciones:

  • Exactamente ci voluntarios pertenecerán a uno de los k grupos del curso i-ésimo.
  • Exactamente gi voluntarios pertenecerán al grupo Gi, en cualquiera de sus n cursos.

A continuación, se muestra un ejemplo de elección de t=6 voluntarios para 4 cursos (filas) y 3 grupos (columnas), donde los requisitos son 1,2,1,2 voluntarios pertenecientes a los cursos 1,2,3,4, y 2,3,1 voluntarios pertenecientes a los grupos G1, G2, G3.

−X−c1=1 
−XXc2=2 
X−−c3=1 
XX−c4=2 
g1=2g2=3g3=1 

donde una “X” indica que el voluntario del curso/grupo correspondiente ha sido escogido por Dumbledore para la misión. Obviamente, se cumple ∑i ci = ∑gi = t.

Se te pide que ayudes a Dumbledore a encontrar el número total de posibles elecciones de voluntarios que satisfagan los criterios impuestos. Dado que este número podría ser muy grande, únicamente te pediremos que nos escribas los últimos 9 dígitos (o sea, el resultado módulo 109).

Entrada

Los números n y k en una línea, separados por espacios, seguidos de una línea con n números c1,…,cn (el número de voluntarios que corresponden a cada curso) y de una línea con k números g1,…,gk (el número de voluntarios que corresponded a cada grupo). Se garantiza que ∑i ci = ∑gi.

Salida

Escribe el número de elecciones de voluntarios, módulo 109, que satisfagan las restricciones.

Puntuación

Diez juegos de prueba con 50 casos cada uno. El juego de pruebas i-ésimo será tal que ningún caso contendrá más de i+2 cursos o grupos. Además, en todos los casos de prueba se pedirán como mucho t≤ 20 voluntarios. Se dará 10 puntos por cada juego de pruebas resuelto.

Public test cases

  • Input

    2 2
0 0
0 0

2 2
0 1
1 0

2 2
1 0
1 0

2 2
2 0
1 1

2 2
2 1
2 1

    Output

    1
1
1
1
1

  • Input

    3 3
1 1 1
1 1 1

3 3
2 1 2
1 3 1

3 3
2 1 1
1 2 1

3 3
0 2 1
1 1 1

    Output

    6
2
5
3

  • Input

    4 4
2 2 2 2
2 2 2 2
6 6
3 3 3 3 3 3
3 3 3 3 3 3
8 8
2 1 2 1 2 1 2 1
1 1 1 1 4 2 1 1
10 10
2 1 2 1 2 1 2 1 2 1
1 1 1 1 4 2 1 1 3 0

    Output

    90
297200
381240
84161700
    • Information
    Author
    Omer Giménez
    Language
    Spanish
    Official solutions
    C++
    User solutions