SPOJ Проблема Флибонакки превышает срок

Question

Я пытаюсь решить эту проблему в Хаскеле, но срок получения превышен. Я применил весь свой Haskell и математические навыки, чтобы оптимизировать это, но все тщетно. Может кто-нибудь предложить мне, как оптимизировать этот код дальше. Последовательность F_3 + F_7 + F_11 .... + F_ (4n + 3) = F_2n * F_ (2n + 1). Я использовал O (log n) для расчета чисел Фибоначчи.

import Data.List
import Data.Maybe
import qualified Data.ByteString.Lazy.Char8 as BS

matmul :: [Integer] -> [Integer] -> Integer -> [Integer]
matmul [a,b,c] [d,e,f] m = [x,y,z] where
    y = (a*e + b*f) `mod` m
    z = (b*e + c*f) `mod` m
    x = y + z


powM ::[Integer] -> Integer -> Integer -> [Integer]
powM a n m | n == 1 = a 
   | n == 2 = matmul a a m
   | even n = powM ( matmul a a m ) ( div n 2 ) m 
   | otherwise = matmul a ( powM ( matmul a a m ) ( div n 2 ) m ) m 

readInt :: BS.ByteString -> Integer
readInt  = fst.fromJust.BS.readInteger 

solve::Integer -> BS.ByteString
solve n = BS.pack.show $ mod ( c*d ) 1000000007 where 
 [c,d,_] = powM [1,1,0] ( 2*n ) 1000000007
--([_,a,_]:_) = powM [[1,2,1],[0,5,3],[0,3,2]] n 1000000007
-- f_3+f_7+f_11+f_15 = f_2n*f_(2n+1)

main = BS.interact $ BS.unlines. map ( solve.readInt ) . tail . BS.lines 

Answer 1

Ваше решение кажется достаточно быстрым, но кажется, что ваша основная функция не печатает ответ после каждой новой строки.На самом деле для получения последнего ответа требуется дополнительная новая строка, так что это может быть причиной вашего тайм-аута!Вот версия, которая печатает каждый ответ сразу после ввода.

import Data.List
import Data.Maybe
import Control.Monad
import qualified Data.ByteString.Lazy.Char8 as B
import qualified Data.ByteString.Char8 as BC
import qualified Text.Show.ByteString as BS

matmul :: [Integer] -> [Integer] -> Integer -> [Integer]
matmul [a,b,c] [d,e,f] m = [x,y,z] where
    y = (a*e + b*f) `mod` m
    z = (b*e + c*f) `mod` m
    x = y + z

powM :: [Integer] -> Integer -> Integer -> [Integer]
powM a n m | n == 1 = a 
   | n == 2 = matmul a a m
   | even n = powM ( matmul a a m ) ( div n 2 ) m 
   | otherwise = matmul a ( powM ( matmul a a m ) ( div n 2 ) m ) m 

solve :: Integer -> Integer
solve n = mod ( c*d ) 1000000007 
  where 
  [c,d,_] = powM [1,1,0] ( 2*n ) 1000000007

readInteger :: B.ByteString -> Integer
readInteger  = fst . fromJust . B.readInteger

readInt :: B.ByteString -> Int
readInt = fst . fromJust . B.readInt

get :: IO B.ByteString
get = liftM (B.fromChunks . (:[])) BC.getLine

main :: IO ()
main = do
  n <- liftM readInt get
  replicateM_ n ( liftM readInteger get >>= B.putStrLn . BS.show . solve )