Fibonacci Sequence

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 1.0s
Memory limit: 64M
Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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


  • 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


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


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


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

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


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

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


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

    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.


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


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

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


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

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


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