My Weblog

Blog about programming and math

SPOJ 7487. Flibonakki

SPOJ 7487. Flibonakki seems hard to be accepted in Haskell. I saw a Java solution accepted so i am hopeful for Haskell. If you are accepted in Haskell or you have better approach for this problem then please let me know. Here are my thoughts for this problem . The idea is again matrix multiplication for linear recurrence.You have to find a relation between N+1 th term and Nth term . Given recurrence G_{n+1} = G_n + F_{4n+3} . F_{4n+3} can be written as 2F_{4n+1} + F_{4n} so our recurrence is G_{n+1} = G_n + 2F_{4n+1} + F_{4n} . Now the only remaining task is to get the matrix form for this recurrence.
\left(\begin{array}{ccc}G_{n+1} \\ F_{4n+5} \\ F_{4n+4}\end{array}\right) = \left(\begin{array}{ccc} 1 & 2 & 1 \\ 0 & 5 & 3 \\ 0 & 3 & 2\end{array}\right) * \left(\begin{array}{ccc}G_{n} \\ F_{4n+1} \\ F_{4n}\end{array}\right) .
Haskell code for this approach.

import Data.List
import qualified Data.ByteString.Char8 as BS
 
matmul ::(Integral a ) => [[a]] -> [[a]] -> a -> [[a]] 
matmul a b m =  map ( \x ->  map ( flip mod m.sum.zipWith (*) x  )   ( transpose  b ) ) a
 

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 x = case BS.readInteger x of
              Just ( i , _ ) -> i
	      Nothing -> error " upseperable ints "
 
solve::Integer -> BS.ByteString
solve n = BS.pack.show $ a where 
	([_,a,_]:_) = powM [[1,2,1],[0,5,3],[0,3,2]] n 1000000007
	
 
main = BS.interact $ BS.unlines. map ( solve.readInt ) . tail . BS.lines 

This code got time limit exceed so after doing a bit of expansion , we can see that it is nothing except F_3 + F_7 + F_11 +...+ F_{4n+3} which is equal to the F_{2n}*F_{2n+1} . See OEIS. Implementation of this approach also got time limit exceed in Haskell so now i am out of ideas. Haskell code for this approach.

import Data.List
import qualified Data.ByteString.Lazy.Char8 as BS


matmul :: [Integer] -> [Integer] -> Integer -> [Integer]
matmul [a,b,c,d] [e,f,g,h] m = [u,v,w,x] where 
	u = mod ( a*e + b*g ) m
	v = mod ( a*f + b*h ) m
	w = mod ( c*e + d*g ) m
	x = mod ( c*f + d*h ) m 

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 x = case BS.readInteger x of
              Just ( i , _ ) -> i
	      Nothing -> error " upseperable ints "

solve::Integer -> BS.ByteString
solve n = BS.pack.show $ c*d where 
	 [c,_,d,_] = powM [1,1,1,0] (2*n) 1000000007
	
main = BS.interact $ BS.unlines. map ( solve.readInt ) . tail . BS.lines 

Advertisements

June 25, 2011 - Posted by | Programming | , , , ,

No comments yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: