2773 - fibona

Cerinţa

Dorel tocmai a aflat despre existenţa şirului lui Fibonacci: F0=0, F1=1, F2=1, F3=2, F4=3, F5=5,… . Pentru numerele n, k şi p date, Dorel vă roagă să calculaţi suma Fp + Fk+p + F2•k+p + … + Fn•k+p.

Date de intrare

Programul citește de la tastatură numerele n , k şi p.

Date de ieșire

Programul va afișa pe ecran suma cerută, modulo 1.000.000.007.

Restricţii şi precizări

• 1 ⩽ n ⩽ 1016
• 0 ⩽ p < k ⩽ 100

Exemplul 1

in

3 3 1 

out

72

Exemplul 2

in

0 1 1 

out

Datele de intrare nu corespund restrictiilor impuse

Rezolvare

<syntaxhighlight lang="python" line> def fibonacci_sum(n_val, k_val, p_val):

   mod = 1000000007
   fib = [0, 1]
   for i in range(2, n_val*k_val+p_val+1):
       fib.append((fib[i-1] + fib[i-2]) % mod)
   return sum(fib[i*k_val+p_val] for i in range(n_val+1)) % mod

def solve_problem(n_val, k_val, p_val):

   if 1 <= n_val <= 10**16 and 0 <= p_val < k_val <= 100:
       print("Datele de intrare corespund restrictiilor impuse")
       return fibonacci_sum(n_val, k_val, p_val)
   else:
       print("Datele de intrare nu corespund restrictiilor impuse")
       return None

n = int(input("Introduceți n: ")) k = int(input("Introduceți k: ")) p = int(input("Introduceți p: "))

print(solve_problem(n, k, p)) </syntaxhighlight>

Explicatie

Suma cerută este F1 + F4 + F7 + F10 = 1 + 3 + 13 + 55 = 72.