Fişierul intrare/ieşire:fibsum.in, fibsum.outSursăRomanian Collegiate Programming Contest 2019
AutorRadu VisanAdăugată deRCPC2019RCPC2019 RCPC2019
Timp execuţie pe test0.3 secLimită de memorie16384 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Fibsum

Se dau T query-uri (left, right) şi se cere calcularea sumei (fibleft + fibleft+1 + ... + fibright) mod 1 000 000 007 pentru fiecare dintre cele T query-uri, unde fibi reprezintă al i-lea termen din şirul lui Fibonacci.

Date de intrare

Fişierul de intrare fibsum.in va conţine T linii, fiecare cu 2 numere naturale left şi right, reprezentând intervalele de query.

Date de ieşire

În fişierul de ieşire fibsum.out va conţine T linii, a i-a linie reprezentând răspunsul pentru al i-lea query.

Restricţii

  • 1 ≤ T ≤ 104
  • 0 ≤ left ≤ right ≤ 109
  • fib0 = fib1 = 1

Exemplu

fibsum.infibsum.out
2
3 5
1 4
16
11

Explicaţie

Primii termeni din şirul lui Fibonacci sunt:
fib0 = 1
fib1 = 1
fib2 = 2
fib3 = 3
fib4 = 5
fib5 = 8

Primul query este peste intervalul [3, 5], cu suma 3 + 5 + 8 = 16. Al doilea query este peste intervalul [1, 4], cu suma 1 + 2 + 3 + 5 = 11.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?