Problema
Un dado standard produce un intero da 1 a 6. Conta tutte le sequenze ordinate non vuote di risultati la cui somma è target. Ordini diversi contano separatamente. Restituisci il conteggio modulo 1.000.000.007.
Implementa dice_combinations(target).
Input
target: La somma richiesta di tutti i lanci.
Output
Restituisci il numero di sequenze modulo 1.000.000.007.
Vincoli
1 ≤ target ≤ 1.000.000. Restituire un conteggio modulo 1.000.000.007 significa restituire il resto della divisione per quel numero.
Esempi
Input:
target = 2
Output atteso:
expected = 2Input:
long long target = 2;
Output atteso:
long long expected = 2;Input:
long target = 2;
Output atteso:
long expected = 2;Spiegazione
Le due sequenze sono [2] e [1, 1].
Input:
target = 4
Output atteso:
expected = 8Input:
long long target = 4;
Output atteso:
long long expected = 8;Input:
long target = 4;
Output atteso:
long expected = 8;Spiegazione
Le sequenze sono [4], [1,3], [3,1], [2,2], [1,1,2], [1,2,1], [2,1,1] e [1,1,1,1].
Come affrontarlo
Prova prima da solo, poi apri un suggerimento alla volta.
Suggerimento 1
Pensa alle somme più piccole come mattoni per costruire il target.
Suggerimento 2
Usa un conteggio cumulativo per ogni somma basato sulle sei somme precedenti.
Suggerimento 3
Applica il modulo a ogni addizione e gestisci separatamente le somme sotto 1.
Complessità attesa
tempo O(target), spazio aggiuntivo O(target)
Riferimenti
Questa sfida è adattata per CodeUtility. Segui la traccia e i vincoli sopra.