Problema
Un dado estándar produce un número entero del 1 al 6. Cuenta todas las secuencias ordenadas no vacías de resultados cuya suma sea igual a target. Secuencias con el mismo contenido pero en distinto orden cuentan como diferentes. Devuelve el conteo módulo 1,000,000,007.
Implementa dice_combinations(target).
Entrada
target: La suma requerida de todos los lanzamientos.
Salida
Devuelve el número de secuencias módulo 1,000,000,007.
Restricciones
1 ≤ target ≤ 1,000,000. Tomar el conteo módulo 1,000,000,007 significa devolver el residuo de la división por ese número.
Ejemplos
Entrada:
target = 2
Salida esperada:
expected = 2Entrada:
long long target = 2;
Salida esperada:
long long expected = 2;Entrada:
long target = 2;
Salida esperada:
long expected = 2;Explicación
Las dos secuencias son [2] y [1, 1].
Entrada:
target = 4
Salida esperada:
expected = 8Entrada:
long long target = 4;
Salida esperada:
long long expected = 8;Entrada:
long target = 4;
Salida esperada:
long expected = 8;Explicación
Las secuencias son [4], [1,3], [3,1], [2,2], [1,1,2], [1,2,1], [2,1,1] y [1,1,1,1].
Cómo abordarlo
Inténtalo primero por tu cuenta y luego abre las pistas una a una.
Pista 1
Piensa en las sumas menores como bloques para construir la suma objetivo.
Pista 2
Usa un conteo acumulado para cada suma basado en las seis sumas anteriores.
Pista 3
Ten cuidado de aplicar el módulo en cada suma y de tratar aparte las sumas menores que 1.
Complejidad esperada
tiempo O(target), espacio extra O(target)
Referencias
Este reto está adaptado para CodeUtility. Sigue el enunciado y las restricciones indicadas arriba.