SPOJ問題Flibonakki時間限制超過

我想在Haskell中解決這個問題problem但時間限制超過。我申請了我所有的Haskell和數學技能來優化這個，但都是徒勞的。有人可以建議我如何進一步優化此代碼。序列F_3 + F_7 + F_11 .... + F_（4n + 3）= F_2n * F_（2n + 1）。我用O（log n）來計算斐波納契數。SPOJ問題Flibonakki時間限制超過

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

來源

2011-06-26 keep_learning

當您使用時間分析，哪些功能最耗時的http：//book.realworldhaskell.org/read/profiling-and-optimization.html#id677833 –

沒有人在Haskell解決了這個，對於這個問題可能太慢了。 –

也許有點memoization會有所幫助。 –

你的解決似乎不夠快，但似乎每一個新行後你的主要功能不打印答案。事實上，它需要額外的換行才能得到最後的答案，所以這可能是超時的原因！這是一個在輸入後直接打印每個答案的版本。

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)

來源

2011-06-27 12:39:53 HaskellElephant

SPOJ問題Flibonakki時間限制超過

回答

相關問題