Problem
Ein Standardwürfel liefert eine ganze Zahl von 1 bis 6. Zähle alle nichtleeren, geordneten Sequenzen von Würfelergebnissen, deren Summe target ist. Verschiedene Reihenfolgen zählen als unterschiedliche Sequenzen. Gib die Anzahl modulo 1.000.000.007 zurück.
Implementiere dice_combinations(target).
Eingabe
target: Die geforderte Summe aller Würfe.
Ausgabe
Gib die Anzahl der Sequenzen modulo 1.000.000.007 zurück.
Einschränkungen
1 ≤ target ≤ 1.000.000. Die Angabe "Anzahl modulo 1.000.000.007" bedeutet, dass der Rest nach Division durch diese Zahl zurückgegeben wird.
Beispiele
Eingabe:
target = 2
Erwartete Ausgabe:
expected = 2Eingabe:
long long target = 2;
Erwartete Ausgabe:
long long expected = 2;Eingabe:
long target = 2;
Erwartete Ausgabe:
long expected = 2;Erläuterung
Die beiden Sequenzen sind [2] und [1, 1].
Eingabe:
target = 4
Erwartete Ausgabe:
expected = 8Eingabe:
long long target = 4;
Erwartete Ausgabe:
long long expected = 8;Eingabe:
long target = 4;
Erwartete Ausgabe:
long expected = 8;Erläuterung
Die Sequenzen sind [4], [1,3], [3,1], [2,2], [1,1,2], [1,2,1], [2,1,1] und [1,1,1,1].
So gehst du vor
Versuch es zuerst allein und öffne dann einen Hinweis nach dem anderen.
Hinweis 1
Denke an kleinere Summen als Bausteine für die Zielsumme.
Hinweis 2
Nutze einen laufenden Wert für jede Summe auf Basis der vorherigen sechs Summen.
Hinweis 3
Achte darauf, das Modulo bei jeder Addition anzuwenden und Summen unter 1 separat zu behandeln.
Erwartete Komplexität
Zeit O(target), zusätzlicher Speicher O(target)
Referenzen
Diese Aufgabe wurde für CodeUtility angepasst. Beachte die oben genannten Vorgaben und Einschränkungen.