Somma di Combinazioni

Dato il valore obiettivo N e un array di numeri positivi consentiti, l’obiettivo è calcolare in quanti modi si può scrivere N come somma di quei numeri.

Ad esempio, se i numeri consentiti sono [1, 2, 3] e il numero N è 4, esistono 7 modi diversi per ottenere la somma di 4:

Tutti e 7 i modi per sommare 1, 2, 3 e ottenere 4

1 + 1 + 1 + 1
1 + 1 + 2
1 + 2 + 1
2 + 1 + 1
1 + 3
3 + 1
2 + 2

Si tratta di un classico problema di programmazione dinamica, risolvibile mantenendo uno stato d[sum] che rappresenta tutti i modi possibili per ottenere la somma sum combinando i numeri consentiti:

N = ...
nums = [...]
d = [0] * (N + 1)          # d[i] = tutte le combinazioni che sommano a i
d[0] = 1                   # C'è un solo modo per ottenere 0: non usare alcun numero

for i in range(1, N + 1):  # Cerca di ottenere tutti i valori in sequenza da 1 a N
    for num in nums:       # Cerca di calcolare d[i] utilizzando num
        if i - num >= 0:   # Se è possibile ottenere i utilizzando num
            d[i] += d[i - num]
print(d[N])

Quindi, d[i] è il numero di modi per ottenere i usando i numeri consentiti nums. Tutti i valori di d si inizializzano a 0, eccetto d[0] che poniamo a 1, poiché 0 si può ottenere soltanto in un modo: non utilizzando alcun numero. Per tutti gli altri numeri, si considerano tutte le possibilità offerte da nums.

Se, per esempio, il numero 11 (d[11]) si può ottenere in 5 modi diversi e il numero 8 (d[8]) si può ottenere in 3 modi, allora, se il numero 3 è presente in nums, possiamo ottenere 11 con tutti i modi trovati fino a quel momento più i modi con cui si ottiene 8 (d[8]), semplicemente aggiungendo 3.

Vediamo un esempio passo dopo passo:

nums = [1, 2, 3] e N = 4

d = [1, 0, 0, 0, 0] → 1 modo per ottenere 0 e 0 per gli altri valori
i = 1
num = 1 ⇒ d[1] += d[0] ⇒ d = [1, 1, 0, 0, 0]
num = 2 ⇒ i - num < 0
num = 3 ⇒ i - num < 0
i = 2
num = 1 ⇒ d[2] += d[1] ⇒ d = [1, 1, 1, 0, 0]
num = 2 ⇒ d[2] += d[0] ⇒ d = [1, 1, 2, 0, 0]
num = 3 ⇒ i - num < 0
i = 3
num = 1 ⇒ d[3] += d[2] ⇒ d = [1, 1, 2, 2, 0]
num = 2 ⇒ d[3] += d[1] ⇒ d = [1, 1, 2, 3, 0]
num = 3 ⇒ d[3] += d[0] ⇒ d = [1, 1, 2, 4, 0]
i = 4
num = 1 ⇒ d[4] += d[3] ⇒ d = [1, 1, 2, 4, 4]
num = 2 ⇒ d[4] += d[2] ⇒ d = [1, 1, 2, 4, 6]
num = 3 ⇒ d[4] += d[1] ⇒ d = [1, 1, 2, 4, 7]
print(d[4]) → stampa 7

Sfida - Combinazioni di dadi

Se lanci un dado, otterrai un numero da 1 a 6. L'obiettivo è calcolare il numero di modi per ottenere il numero n sommando i risultati dei lanci del dado.

Input

L’input contiene un singolo intero n (1 ≤ n ≤ ).

Output

Il programma deve stampare il numero di modi in cui si può ottenere n come somma dei lanci di dado. Poiché il risultato può diventare molto grande, deve essere stampato modulo .

Esempi

Input	Output
2	2
3	4

Spiegazione

2 → 1 + 1, 2
3 → 1 + 1 + 1, 1 + 2, 2 + 1, 3

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB