21 lines
703 B
Haskell
21 lines
703 B
Haskell
import Data.Array
|
|
import Data.Int (Int64)
|
|
|
|
q = qq [listArray (1,2) [1,1]] 1 where
|
|
qq a n = seek aa n : qq aa (1 + n) where
|
|
aa | n <= l = a
|
|
| otherwise = listArray (l+1,l*2) (take l $ drop 2 lst):a
|
|
where
|
|
l = snd (bounds $ head a)
|
|
lst = seek a (l-1):seek a l:(ext lst (l+1))
|
|
ext (q1:q2:qs) i = (g (i-q2) + g (i-q1)):ext (q2:qs) (1+i)
|
|
g = seek aa
|
|
seek (ar:ars) n
|
|
| n >= fst (bounds ar) = ar ! n
|
|
| otherwise = seek ars n
|
|
|
|
-- Only a perf test. Task can be done exactly the same as above
|
|
main = print $ sum qqq
|
|
where
|
|
qqq :: [Int64]
|
|
qqq = map fromIntegral $ take 3000000 q
|