Fast Fibonacci Mod
Python
Hard
5 views
Problem Description
For each testcase you get n. Output Fibonacci(n) modulo 1000000007. Use fast doubling so big n is also ok.
Input Format
First integer t. Next t lines n.
Output Format
t lines fib mod.
Official Solution
import sys
MOD=1000000007
p=sys.stdin.read().strip().split()
if not p:
sys.exit(0)
it=iter(p)
t=int(next(it))
def fib(n):
if n==0:
return (0,1)
a,b=fib(n>>1)
c=(a*((2*b-a)%MOD))%MOD
d=(a*a+b*b)%MOD
if n&1:
return (d,(c+d)%MOD)
return (c,d)
out=[]
for _ in range(t):
n=int(next(it))
out.append(str(fib(n)[0]))
sys.stdout.write('\
'.join(out))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!