Dubbio su "Lotteria"

Ciao, sto cercando di risolvere lotteria, ma non riesco a capire come mai la mia soluzione non funziona.

Premetto che ho dato solo una rapida occhiata alla soluzione ufficiale, tralasciandone diverse parti, dunque ne ho appena una vaga idea.

Comunque, la mia soluzione (che dovrebbe essere O(n*m)) si basa sostanzialmente su una funzione calcola(n,m) (definita per n,m > 0), la quale restituisce il numero di sequenze che ci interessano di lunghezza n e aventi i termini <= m, definita per ricorrenza come segue:
calcola(n,m) =
  • 1 se n = 1
  • 0 se m < 2^(n-1)
  • somma per i che varia da 2^(n-1) a m di calcola(n-1,[i/2])
dove [x] è la parte intera di x.

Ora, non solo totalizza 0 punti, ma la cosa strana è che non risolve neppure un’istanza del Subtask 2, mentre ne prende alcune dei Subtask 3 e 4. Eppure ho fatto decine di test in locale e sembra che per valori non troppo alti funzioni…

Ti sei ricordato di ritornare il risultato modulo 1000000007? Ho perso mezz’ora a causa di quella dimenticanza…

Sì, chiaramente nell’implementazione c’è il modulo… E in ogni caso le istanze del Subtask 2 dovrebbero avere tutte soluzioni minori di quel numero.

[...] il numero di sequenze che ci interessano di lunghezza n e aventi i termini <= m, definita per ricorrenza come segue:
calcola(n,m) =
  • 1 se n = 1

cip999

uhm... sicuro?
[...] il numero di sequenze che ci interessano di lunghezza n e aventi i termini <= m, definita per ricorrenza come segue:
calcola(n,m) =
  • 1 se n = 1

cip999

uhm... sicuro?

wil93

Ok, dunque ho perso un pomeriggio pensando che le liste dovessero iniziare per 1??? :O
Grazie per avermi illuminato, ora correggo e spero funzioni... :)