View source for 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 &les; n &les; 1016'''
* '''0 &les; p < k &les; 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.