Fibonacci Sequence

View as PDF
Submit solution
Points: 15 (partial)
Time limit: 2.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


  • 3
    MingqiHuang  commented on June 4, 2018, 3:16 a.m.

    Use unsigned long long for C or C++ or you will get WA in the last testcase, sadly.


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


  • 0
    crackersamdjam  commented on May 15, 2018, 8:09 p.m.

    Tim, it's not there. The code works fine on my machine


  • 0
    crackersamdjam  commented on May 14, 2018, 10:38 p.m.

    Hey Dmoj, Does anyone know what RTE(aborted) means? Thanks


  • 3
    rsylshzxdkh  commented on Aug. 22, 2017, 2:29 p.m. ← edited

    Help

    Java TLE

    Never mind I got it


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


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


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

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


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

    @global_smurf


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

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


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


  • -3
    DanAlexanderIlicio  commented on Aug. 6, 2015, 12:20 a.m.

    I have no idea how to do the Sequence. In my algorithm first, module Output (d=n% 1 000 000 0007) , after sending the result to the method:

    static int mo=1000000007;
static int fib(int d){
     int x = 0, y = 1, z = 1;
    for (long i = 0; i < d; i++) {
        x = y%mo;
        y = z;
        z = x + y;
            z=z%mo;
    }
    return x;
}

    But still very it slow when passing a very large number as d= 333 333 716 .


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


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


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


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

      So shouldn't this also be tagged dp?


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