Fibonacci Sequence

View as PDF
Submit solution
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 (1 \le N \le 10^{19}), find the N^{th} Fibonacci number, modulo 1\,000\,000\,007 (= 10^9 + 7).

Note: For 30% of the marks of this problem, it is guaranteed that (1 \le N \le 1\,000\,000).

Input Specification

The first line of input will have the number N.

Output Specification

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

Sample Input

26

Sample Output

121393

Comments


  • 0
    YassirSalama  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?


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

      You'll need to take a fundamentally different approach- \mathcal O(n) is too slow for this problem.


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

      Given a number N, find the Nth Fibonacci number, modulo 1000000007.

      Note that N can be very large - 10^{19}


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


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

            Ah, it worked, thanks!


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


  • 4
    Darcy_Liu  commented on May 7, 2019, 4:49 p.m. ← edit 2

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


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

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


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

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


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

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


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

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


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

    The problem requires you to output mod 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. 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 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):

    \displaystyle \begin{align*} (a + b) \bmod m &\equiv ((a \bmod m) + (b \bmod m)) \bmod m \\ (a \times b) \bmod m &\equiv ((a \bmod m) \times (b \bmod m)) \bmod m \end{align*}


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


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

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


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