# Untitled

By: a guest on Jun 10th, 2012  |  syntax: None  |  size: 1.92 KB  |  hits: 21  |  expires: Never
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
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
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