杭电的1005题 我不需要代码 请各位给我讲讲思路和做法

杭电的1005题 我不需要代码 请各位给我讲讲思路和做法
A number sequence is defined as follows:
f(1) =
1,f(2) = 1,f(n) = (A * f(n - 1) + B * f(n - 2)) mod 7.
Given A,B,and
n,you are to calculate the value of f(n).
如果就按它那么写的话会超时
我知道有很多解题报告 但是我想请你们先给我讲讲思路 然后我再试着自己去尝试
我将长大 1年前 已收到1个回答 举报

opensonic 幼苗

共回答了18个问题采纳率:94.4% 举报

这题的关键就在于时间,因为n可能很大很大.
但因为有mod 7,所以f(n)取值是0-6,共7个取值,而f(n)又由f(n-1) 和 f(n-2)两个决定,因此最多有7*7=49种可能的组合,因此在50以内必然出现循环,
所以我们用数组模拟前49组数组,后面的数据只要mod (模除)循环节就可以了,对应的的数组里头取值

1年前

7
可能相似的问题
Copyright © 2024 YULUCN.COM - 雨露学习互助 - 16 q. 0.030 s. - webmaster@yulucn.com