SPOJ Problema Flibonakki límite de tiempo excede

Question

Estoy tratando de resolver este problem en Haskell pero superando el límite de tiempo. Apliqué todo mi Haskell y la habilidad matemática para optimizar esto, pero todo fue en vano. ¿Podría alguien por favor sugerirme cómo optimizar este código aún más? La secuencia F_3 + F_7 + F_11 .... + F_ (4n + 3) = F_2n * F_ (2n + 1). Usé el método O (log n) para calcular los números de Fibonacci.

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

Su solución parece ser lo suficientemente rápido pero parece que su función principal no se imprime la respuesta después de cada nueva línea. De hecho, requiere una nueva línea adicional para obtener la última respuesta, ¡así que esta puede ser la causa de su tiempo de espera! Aquí hay una versión que imprime cada respuesta directamente después de la entrada.

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)