Alle Herausforderungen
Mittel 1 gelöst 25.0% Erfolgsquote

Würfelsequenzen zählen

Zähle geordnete Würfelsequenzen mit einer gegebenen Gesamtsumme.

Das lernst du

  • Antworten aus kleineren Summen aufbauen
  • Eine Rekursion über den letzten Wurf schreiben
  • Ergebnisse modulo einer großen Primzahl nehmen

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

Beispiel 1
Eingabe:
target = 2

Erwartete Ausgabe:
expected = 2
Eingabe:
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].

Beispiel 2
Eingabe:
target = 4

Erwartete Ausgabe:
expected = 8
Eingabe:
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.

Die beste bestandene Lösung jedes Coders. Schnellere, sparsamere und besser bewertete Lösungen stehen weiter oben.

# Coder Sprache Zeit Speicher KI-Bewertung Lösung
1 ННикита Python 973 ms - 5/5 Code ansehen

Von anderen lernen

Community-Lösungen

Achtung Spoiler: 1 vollständige Lösung unten Versuche es zuerst selbst zu lösen. Du kannst trotzdem einen Blick auf den Code und die KI-Reviews anderer Entwickler werfen. Melde dich an und löse die Aufgabe, um an der Diskussion teilzunehmen.