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

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))

Explicatie

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