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 May 20, 2022, 4:08 p.m.

I used dp but doesn't work with larger inputs, I need to use bitnet or what?

• commented on May 20, 2022, 7:41 p.m.

You'll need to take a fundamentally different approach- is too slow for this problem.

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

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. edit 2

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

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

This comment is hidden due to too much negative feedback. Show it anyway.

• 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. Show it anyway.

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

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

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

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 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. Show it anyway.

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