Fibonacci modulo
Compute the n-th Fibonacci number modulo m using the fast-doubling method (O(log n)), where F(0)=0, F(1)=1. Constraints: 0 <= n <= 10^18, 1 <= m <= 10^9. A linear loop would be far too slow for n near 10^18, so use the doubling identities F(2k)=F(k)*(2*F(k+1)-F(k)) and F(2k+1)=F(k+1)^2+F(k)^2.
Implement
fib_mod(n: int, m: int) → intExamples
in
[10,1000000007]out55What a strong answer looks like
State your approach and its time/space complexity out loud before you optimize. Handle the edge cases (empty input, duplicates, overflow), and say why you chose this over the brute force. Green tests are the floor, not the grade.
0:00 of about 35 min
solution.py
InputExpectedGot
[10,1000000007]55not run yetsample