ACM题目,求思路?According to a research,VIM users tend to have shorter fingers,compared with Emacs users.  Hence they prefer problems short,too.Here is a short one:  Given n (1

来源:学生作业帮助网 编辑:作业帮 时间:2024/05/09 18:24:19
ACM题目,求思路?According to a research,VIM users tend to have shorter fingers,compared with Emacs users.  Hence they prefer problems short,too.Here is a short one:  Given n (1

ACM题目,求思路?According to a research,VIM users tend to have shorter fingers,compared with Emacs users.  Hence they prefer problems short,too.Here is a short one:  Given n (1
ACM题目,求思路?
According to a research,VIM users tend to have shorter fingers,compared with
Emacs users.
  Hence they prefer problems short,too.Here is a short
one:
  Given n (1

ACM题目,求思路?According to a research,VIM users tend to have shorter fingers,compared with Emacs users.  Hence they prefer problems short,too.Here is a short one:  Given n (1
用查表法,用数组记录下1000活着10000个gn的值(g(0)-g(1000))这个具体多少看情况办,然后应该可以证明出g(g(n))mod 109=g(n) mod 109 (这个因为没细看,所以不知道是不是正确的,但是一般来说,这种题目都暗含这种公式,应该是可以证明出来的)
然后你记录数组的时候实际上记录的是g(n)=g(n) mod 109,也就是时候,每个下标对应的g(n)值,实际上是处理过后(g(n) mod 109)的g(n)值(不然很可能会越界)
然后因为你已经有个这么多个g(n)的值了,所以你计算的时候不需要递归,可以直接查表就能得到值了
大概思路就这样