Chaînes de bits « belles »
Nous aimons beaucoup les chaînes de bits (bit-strings). Nous considérons qu’une chaîne de bits est « belle » si elle ne contient pas
k zéros consécutifs. Étant donné une longueur n, pouvez-vous déterminer combien de chaînes de bits distinctes de longueur n satisfont à ce critère ?Entrée
Les données d’entrée contiennent deux entiers
n et k (1 ≤ k ≤ n ≤ 1000).Sortie
Le programme doit afficher le nombre de chaînes de bits « belles » de longueur
n. Comme la réponse peut être très grande, vous devez l’afficher modulo .Exemples
Entrée | Sortie |
5 2 | 24 |
Explication
- 00100
- 00101
- 00110
- 00111
- 01001
- 01010
- 01011
- 01100
- 01101
- 01110
- 01111
- 10010
- 10011
- 10100
- 10101
- 10110
- 10111
- 11001
- 11010
- 11011
- 11100
- 11101
- 11110
- 11111
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB