Problema
Um dado padrão produz um inteiro de 1 a 6. Conte todas as sequências ordenadas não vazias de resultados cuja soma seja igual a target. Ordens diferentes contam separadamente. Retorne a contagem módulo 1.000.000.007.
Implemente dice_combinations(target).
Entrada
target: A soma requerida de todos os lançamentos.
Saída
Retorne o número de sequências módulo 1.000.000.007.
Restrições
1 ≤ target ≤ 1.000.000. Retornar a contagem módulo 1.000.000.007 significa retornar o resto da divisão desse valor por esse número.
Exemplos
Entrada:
target = 2
Saída esperada:
expected = 2Entrada:
long long target = 2;
Saída esperada:
long long expected = 2;Entrada:
long target = 2;
Saída esperada:
long expected = 2;Explicação
As duas sequências são [2] e [1, 1].
Entrada:
target = 4
Saída esperada:
expected = 8Entrada:
long long target = 4;
Saída esperada:
long long expected = 8;Entrada:
long target = 4;
Saída esperada:
long expected = 8;Explicação
As sequências são [4], [1,3], [3,1], [2,2], [1,1,2], [1,2,1], [2,1,1] e [1,1,1,1].
Como abordar
Tente sozinho primeiro e depois abra uma dica de cada vez.
Dica 1
Pense nas somas menores como blocos de construção para a soma alvo.
Dica 2
Use uma contagem acumulada para cada soma com base nas seis somas anteriores.
Dica 3
Cuidado para aplicar o módulo em cada adição e tratar separadamente as somas abaixo de 1.
Complexidade esperada
tempo O(target), espaço extra O(target)
Referências
Este desafio foi adaptado para o CodeUtility. Siga o enunciado e as restrições acima.