SPOJ Sorun Flibonakki zaman sınırı ı Haskell bu <a href="http://www.spoj.pl/problems/FLIB/" rel="nofollow">problem</a> çözmeye çalışıyorum ama almak zaman sınırı aşan

Question

aşar. Bunu optimize etmek için tüm Haskell ve matematik becerilerimi kullanıyorum ama hepsi boşuna. Birisi lütfen bu kodu nasıl optimize edeceğimi önerebilir. dizisi F_3 + F_7 + F_11 .... + F_ (4n + 3) = F_2n * F_ (2n + 1). Fibonacci sayılarını hesaplamak için O (log n) metodunu kullandım.

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

Çözmeniz yeterince hızlı görünüyor ancak ana işlevinizin her yeni satırdan sonra yanıt yazmaması gibi görünüyor. Aslında son cevabı almak için ekstra bir satır gerektirir, bu da zaman aşımının sebebi olabilir! İşte her cevap doğrudan girişten sonra yazdırılan bir sürüm.

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)