Problème
Un dé standard produit un entier de 1 à 6. Comptez toutes les séquences ordonnées non vides de résultats dont la somme est égale à target. Les ordres différents comptent séparément. Retournez le nombre de séquences modulo 1 000 000 007.
Implémentez dice_combinations(target).
Entrée
target : La somme requise de tous les lancers.
Sortie
Retournez le nombre de séquences modulo 1 000 000 007.
Contraintes
1 ≤ target ≤ 1 000 000. Prendre un compte modulo 1 000 000 007 signifie retourner son reste après division par ce nombre.
Exemples
Entrée :
target = 2
Sortie attendue :
expected = 2Entrée :
long long target = 2;
Sortie attendue :
long long expected = 2;Entrée :
long target = 2;
Sortie attendue :
long expected = 2;Explication
Les deux séquences sont [2] et [1, 1].
Entrée :
target = 4
Sortie attendue :
expected = 8Entrée :
long long target = 4;
Sortie attendue :
long long expected = 8;Entrée :
long target = 4;
Sortie attendue :
long expected = 8;Explication
Les séquences sont [4], [1,3], [3,1], [2,2], [1,1,2], [1,2,1], [2,1,1] et [1,1,1,1].
Comment l'aborder
Essayez d'abord seul, puis ouvrez les indices un par un.
Indice 1
Considère les petites sommes comme des briques pour construire la cible.
Indice 2
Utilise un comptage courant pour chaque somme à partir des six sommes précédentes.
Indice 3
Attention à appliquer le modulo à chaque addition et à traiter séparément les sommes inférieures à 1.
Complexité attendue
temps O(target), espace supplémentaire O(target)
Références
Ce défi a été adapté pour CodeUtility. Suivez l'énoncé et les contraintes ci-dessus.