## Fibonacci Sequence

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M

Problem type

The Fibonacci sequence is a well known sequence of numbers in which Given a number  , find the Fibonacci number, modulo  .
Note: For 30% of the marks of this problem, it is guaranteed that .

#### Input Specification

The first line of input will have the number .

#### Output Specification

The Fibonacci number, modulo  .

#### Sample Input

26

#### Sample Output

121393

• commented on Sept. 3, 2021, 8:42 a.m. edited

[deleted]

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

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

• 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.

• commented on April 11, 2021, 11:35 a.m. edit 2

Given a number , find the th Fibonacci number, modulo .

Note that can be very large -  • 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

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

Try Solving the Fibonacci Sequence with Matrix Exponentiation

• 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.

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

What should I use for input then?

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

You can read the input using unsigned long long.

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

Ah, it worked, thanks!

• 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.

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

You should try testing your code with large test cases. For example, .

• commented on May 7, 2019, 4:49 p.m. edited

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

• 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;

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

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

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

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

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

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

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

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

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

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

• 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.

• commented on May 27, 2015, 8:06 p.m. edited

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

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

This is not a recursive problem.

• commented on Sept. 15, 2014, 9:16 p.m.

The problem requires you to output mod . That means that you need to get the remainder of the final answer when it is divided by . 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 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):  • 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 .

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

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

• 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.