Don't like ads? PRO users don't see any ads ;-)
Public Pastes
Guest

Untitled

By: a guest on Jun 10th, 2012  |  syntax: None  |  size: 1.92 KB  |  hits: 21  |  expires: Never
download  |  raw  |  embed  |  report abuse  |  print
Text below is selected. Please press Ctrl+C to copy to your clipboard. (⌘+C on Mac)
  1. SPOJ Problem Flibonakki time limit exceed
  2. import Data.List
  3. import Data.Maybe
  4. import qualified Data.ByteString.Lazy.Char8 as BS
  5.  
  6. matmul :: [Integer] -> [Integer] -> Integer -> [Integer]
  7. matmul [a,b,c] [d,e,f] m = [x,y,z] where
  8.     y = (a*e + b*f) `mod` m
  9.     z = (b*e + c*f) `mod` m
  10.     x = y + z
  11.  
  12.  
  13. powM ::[Integer] -> Integer -> Integer -> [Integer]
  14. powM a n m | n == 1 = a
  15.    | n == 2 = matmul a a m
  16.    | even n = powM ( matmul a a m ) ( div n 2 ) m
  17.    | otherwise = matmul a ( powM ( matmul a a m ) ( div n 2 ) m ) m
  18.  
  19. readInt :: BS.ByteString -> Integer
  20. readInt  = fst.fromJust.BS.readInteger
  21.  
  22. solve::Integer -> BS.ByteString
  23. solve n = BS.pack.show $ mod ( c*d ) 1000000007 where
  24.  [c,d,_] = powM [1,1,0] ( 2*n ) 1000000007
  25. --([_,a,_]:_) = powM [[1,2,1],[0,5,3],[0,3,2]] n 1000000007
  26. -- f_3+f_7+f_11+f_15 = f_2n*f_(2n+1)
  27.  
  28. main = BS.interact $ BS.unlines. map ( solve.readInt ) . tail . BS.lines
  29.        
  30. import Data.List
  31. import Data.Maybe
  32. import Control.Monad
  33. import qualified Data.ByteString.Lazy.Char8 as B
  34. import qualified Data.ByteString.Char8 as BC
  35. import qualified Text.Show.ByteString as BS
  36.  
  37. matmul :: [Integer] -> [Integer] -> Integer -> [Integer]
  38. matmul [a,b,c] [d,e,f] m = [x,y,z] where
  39.     y = (a*e + b*f) `mod` m
  40.     z = (b*e + c*f) `mod` m
  41.     x = y + z
  42.  
  43. powM :: [Integer] -> Integer -> Integer -> [Integer]
  44. powM a n m | n == 1 = a
  45.    | n == 2 = matmul a a m
  46.    | even n = powM ( matmul a a m ) ( div n 2 ) m
  47.    | otherwise = matmul a ( powM ( matmul a a m ) ( div n 2 ) m ) m
  48.  
  49. solve :: Integer -> Integer
  50. solve n = mod ( c*d ) 1000000007
  51.   where
  52.   [c,d,_] = powM [1,1,0] ( 2*n ) 1000000007
  53.  
  54. readInteger :: B.ByteString -> Integer
  55. readInteger  = fst . fromJust . B.readInteger
  56.  
  57. readInt :: B.ByteString -> Int
  58. readInt = fst . fromJust . B.readInt
  59.  
  60. get :: IO B.ByteString
  61. get = liftM (B.fromChunks . (:[])) BC.getLine
  62.  
  63. main :: IO ()
  64. main = do
  65.   n <- liftM readInt get
  66.   replicateM_ n ( liftM readInteger get >>= B.putStrLn . BS.show . solve )
create a new version of this paste RAW Paste Data