Blue Bridge Cup Based on practice Fibonacci The sequence python

• Resource constraints
• Problem description
• Input format
• Output format
• The sample input
• Sample output
• The sample input
• Sample output
• Data scale and agreement
• Implementation code
• matters needing attention

Resource constraints

The time limit ：1.0s Memory limit ：256.0MB

Problem description

Fibonacci The recurrence formula of sequence is ：Fn=Fn-1+Fn-2, among F1=F2=1.

When n The larger the ,Fn It's also very large. , Now we want to know ,Fn Divide 10007 What is the remainder of .

Input format

Input contains an integer n.

Output format

Output one line , Contains an integer , Express Fn Divide 10007 The remainder of .

The sample input

10

Sample output

55

The sample input

22

Sample output

7704

Data scale and agreement

1 <= n <= 1,000,000.

Implementation code

f1=1
f2=1
n=int(input())
if n==1 or n==2:
print(f1%10007)
else:
for i in range(n-2):
f=(f1+f2)%10007
f1=f2
f2=f
print(f)

Error code

f1=1
f2=1
n=int(input())
if n==1 or n==2:
print(f1%10007)
else:
for i in range(n-2):
f=f1+f2
f1=f2
f2=f
print((f)%10007)

matters needing attention

This topic seems simple, but in fact, it is hidden Fibonacci The sequence The amount of recursive data is huge n When it is large, the timeout problem will occur , This question has given us hints in the problem description “ When n The larger the ,Fn It's also very large. , Now we want to know ,Fn Divide 10007 What is the remainder of .”Fn Very big and what we need to know is Fn Divide 10007 So it suggests that we can bypass the solution Fn Get the answer directly . And the remainder before recursion does not affect the result . Therefore, the remainder before recursion reduces the amount of computation .