4032 - Zar 1

Cerința

În câte moduri se poate obține suma n aruncând cu zarul (În câte moduri poți să îl scrii pe n ca sumă de valori mai mici sau egale cu 6).

Date de intrare

Programul citește de la tastatură numărul n.

Date de ieșire

Programul va afișa pe ecran răspunsul la întrebarea din enunț.

Restricții și precizări

1≤n≤1018 Rezultatul se va afișa modulo 109+7 . ==Exemplu==: Intrare

8 Ieșire

125

Explicație

Câteva dintre posibilități ar fi 1 + 1 + 6, 2 + 5 + 1, 1 + 6 + 1 …

Rezolvare

<syntaxhighlight lang="python3"> MOD = 10**9 + 7

def numar_moduri_suma(n):

  # Initializăm lista cu 0-uri
  dp = [0] * (n + 1)
  # Există o singură modalitate de a obține suma 0, adică nu aruncăm zarul
  dp[0] = 1
  # Calculăm numărul de moduri pentru fiecare sumă posibilă
  for i in range(1, n + 1):
      for j in range(1, 7):
          if i - j >= 0:
              dp[i] = (dp[i] + dp[i - j]) % MOD
  return dp[n]

if __name__ == "__main__":

  n = int(input("Introduceți suma n: "))
  rezultat = numar_moduri_suma(n)
  print(rezultat)

</syntaxhighlight>