Climbing a Staircase of a Billion Billion Steps
A staircase has n steps and each move climbs 1 or 2 of them. Count the distinct ways to
reach the top, modulo 1000000007.
4 steps -> 5
10 steps -> 89
## The recurrence is right and the loop is not
ways(n) = ways(n-1) + ways(n-2), which is problem 401 and the Fibonacci numbers. The loop
over n is O(n) and uses two variables, which is as tidy as a dynamic program gets.
Here n reaches 10^18. A loop doing one addition per step, at a billion steps a second,
finishes in about 30 years.
So the recurrence is kept and the way it is EVALUATED changes. That is the distinction this problem exists for: "the DP is wrong" and "the loop is wrong" are different complaints, and only the second applies.
## One step in logarithmic time
Two identities let the index be halved instead of decremented:
F(2i) = F(i) * (2*F(i+1) - F(i))
F(2i+1) = F(i)^2 + F(i+1)^2
Applied from the top bit of n downwards, they reach F(n) in about 60 steps. With
F(1) = F(2) = 1, the answer is F(n+1).
The same thing can be done with a 2 by 2 matrix raised to the power n by repeated squaring,
which is easier to remember and about four times the multiplications. Either is fine at this
size.
## Subtraction under a modulus
2*F(i+1) - F(i) can come out negative once the values are reduced. Add the modulus back
before multiplying, or the result is wrong in a language where % keeps the sign of the left
operand. That is C, C++, Java and JavaScript; Python is the exception.
This is the single most common bug in fast doubling, and it only shows up on large inputs, which is exactly where it is hardest to notice.
## Reading n
10^18 fits in a signed 64 bit integer and does not fit exactly in a double. In JavaScript
read it as a big integer; Number(...) silently rounds.
## A value worth keeping
n = 1000000007 answers 0. That is not a bug: some Fibonacci number really is a multiple of
the modulus, and an implementation that special-cases a zero result will fail this test.
## Boundaries
n = 1 answers 1 and n = 2 answers 2. Getting the offset right, that is F(n+1) rather than
F(n), is most of what goes wrong on the small cases.
## Cost
Time O(log n). Space O(log n) for the recursion, or O(1) iteratively.