Fibonacci Sequence

Points: 15 (partial)

Time limit: 1.0s

Memory limit: 64M

Problem type

The Fibonacci sequence is a well known sequence of numbers in which

$\displaystyle F(n) = \begin{cases} 0, & \text{if } n = 0 \\ 1, & \text{if } n = 1 \\ F(n-2) + F(n-1), & \text{if } n \ge 2 \end{cases}$

Given a number $N$ ~N~ $(1 \le N \le 10^{19})$ ~(1 \le N \le 10^{19})~, find the $N^{th}$ ~N^{th}~ Fibonacci number, modulo $1\,000\,000\,007$ ~1\,000\,000\,007~ $(= 10^9 + 7)$ ~(= 10^9 + 7)~.
Note: For 30% of the marks of this problem, it is guaranteed that $(1 \le N \le 1\,000\,000)$ ~(1 \le N \le 1\,000\,000)~.

Input Specification

The first line of input will have the number $N$ ~N~.

Output Specification

The $N^{th}$ ~N^{th}~ Fibonacci number, modulo $1\,000\,000\,007$ ~1\,000\,000\,007~ $(= 10^9 + 7)$ ~(= 10^9 + 7)~.

Sample Input

Sample Output

Comments

0

dchoo333 commented on Sept. 3, 2021, 8:42 a.m. ← edited →

[deleted]

0

d commented on Sept. 3, 2021, 1:22 p.m.

225851433717 is the 56th Fibonacci number. I doubt that you solve the sample input correctly.

-1

JAREDZHOUBIGBOI commented on April 11, 2021, 11:06 a.m.

What are we trying to solve? Sry I'm new to Dmoj so it's kinda confusing.

1

Badmode commented on April 11, 2021, 11:35 a.m. ← edit 2 →

Given a number $N$ ~N~, find the $N$ ~N~th Fibonacci number, modulo $1000000007$ ~1000000007~.

Note that $N$ ~N~ can be very large - $10^1$ ~10^1~ $^9$ ~^9~

3

Pleedoh commented on May 31, 2019, 1:19 p.m. ← edited →

Any ideas on how to cut down on the recursive calls and avoid a stack overflow on the last case?

Edit: Avoid MLE

-1

Tommy_Shan commented on Oct. 13, 2021, 11:28 a.m.

Try Solving the Fibonacci Sequence with Matrix Exponentiation

3

Beautiful_Times commented on May 31, 2019, 2:06 p.m.

If im reading your code, you are reading in a long while the max value is above a long. Avoid using a long for input.

1

Pleedoh commented on June 3, 2019, 1:24 p.m.

What should I use for input then?

7

zxyl commented on June 3, 2019, 2:16 p.m.

You can read the input using unsigned long long.

1

Pleedoh commented on June 5, 2019, 12:40 a.m.

Ah, it worked, thanks!

0

narasreeram commented on May 30, 2019, 4:04 p.m.

For some reason, my code doesn't work on this platform but it does on every other platform and all my test cases are right.

2

wleung_bvg commented on May 30, 2019, 5:03 p.m.

You should try testing your code with large test cases. For example, $N = 10^{19}$ ~N = 10^{19}~.

5

Darcy_Liu commented on May 7, 2019, 4:49 p.m. ← edited →

The 10^19 overflowed my scanf need to use scanf("%llu",&n);

-4

kingW3 commented on May 30, 2018, 1:02 p.m. ← edited →

In C++ if you're using map for memoization for example F[n] = fib(n-1)+fib(n-2) then F[n] may be created before the fib(n-1)+fib(n-2) returns a value, so better use something like a = fib(n-1)+fib(n-2); then F[n] = a;

-14

sunnylancoder commented on March 20, 2017, 11:02 p.m.

They said it couldn't be done - 0.02 seconds AC

oh yeah mr krabbs I beet quantum!

This comment is hidden due to too much negative feedback. Click here to view it.

-13

sunnylancoder commented on Dec. 5, 2016, 11:05 p.m.

Requires basic math knowledge, but I mainly solved it by observation/logic.

This comment is hidden due to too much negative feedback. Click here to view it.

9

r3mark commented on Dec. 5, 2016, 11:15 p.m.

The intended solution uses matrices which is considered advanced math for DMOJ tags.

-7

aCookieBreak commented on June 15, 2016, 8:33 p.m.

@global_smurf

This comment is hidden due to too much negative feedback. Click here to view it.

0

Kirito commented on June 15, 2016, 8:40 p.m.

r3mark hijacked global smurf cuz he submiited some 15+ pointers on it.

-4

r3mark commented on Nov. 28, 2015, 11:41 a.m. ← edit 2 →

This submission was submitted in December 2015. https://dmoj.ca/submission/25109 https://gyazo.com/384dbe04e5e09316b99739e7eb9497ca

Edit: Fixed, timestamp now says 2014.

-12

Tan commented on May 27, 2015, 8:06 p.m. ← edited →

NVM

This comment is hidden due to too much negative feedback. Click here to view it.

8

BMP commented on May 27, 2015, 9:58 p.m.

This is not a recursive problem.

18

arock commented on May 27, 2015, 8:19 p.m.

https://www.ics.uci.edu/~eppstein/161/960109.html

21
FatalEagle commented on Sept. 15, 2014, 9:16 p.m.
The problem requires you to output mod $1\,000\,000\,007$ ~1\,000\,000\,007~. That means that you need to get the remainder of the final answer when it is divided by $1\,000\,000\,007$ ~1\,000\,000\,007~. This operation can be done in Python, C++, and Java by using '%'.

Example: 999999999999999999999999 mod 1000000007 is 999999999999999999999999 % 1000000007 which is equal to 48999999. Because 999999999999999999999999 = 999999993000000 * 1000000007 + 48999999, 48999999 is 999999999999999999999999 (mod 1000000007).

It may interest you to know that $1\,000\,000\,007$ ~1\,000\,000\,007~ is a prime number.

There are a two highly useful properties of modular arithmetic we often use in programming competitions (% has the same precedence as multiplication and division):

$(a\ +\ b)\ \textrm{mod}\ m \equiv ((a\ \textrm{mod}\ m) + (b\ \textrm{mod}\ m))\ \textrm{mod}\ m$

$(a\ \times\ b)\ \textrm{mod}\ m \equiv ((a\ \textrm{mod}\ m) \times (b\ \textrm{mod}\ m))\ \textrm{mod}\ m$

12

quantum commented on Sept. 13, 2014, 4:30 p.m. ← edited →

This problem is a lot more difficult than it may appear. There is a reason for 15 points. The input can be as big as $10^{19}$ ~10^{19}~.

-7

Arihan10 commented on Feb. 6, 2019, 5:29 p.m.

So shouldn't this also be tagged dp?

This comment is hidden due to too much negative feedback. Click here to view it.

7

Zeyu commented on Feb. 6, 2019, 6:36 p.m.

The typical dynamic programming solution will not pass the larger inputs. More math insights is used in the solution rather than dynamic programming.