My Weblog

Blog about programming and math

SPOJ 5294. Recurrence

SPOJ 5294. Recurrence is really nice problem . I tried to solve this problem a year ago and got time limit exceed. Initially i got the close form of F_n= a^n+b(1+a+a^2.......+a^{n-1}) and wrote a Haskell solution which got TLE but its worth sharing the code because i learned how to calculate sum to geometric series a + ar + ar^2 + ar^3  + .....+ ar^{n-1} mod m without calculating the inverse of m with respect to r. Sum of geometric series will be \frac {a*(r^n-1)} {r-1} mod m . You can see analysis at codechef for solving this problem.The last paragraph suggests that we can write it as if n is even then (1+r^{\frac n 2})*(1+r+r^2+....+r^{\frac {n-1} 2} ) and if n is odd then we have to add the last term r^{n-1} to this sum. This way we can calculate the whole sum in O(\log n ) if we don’t care the calculation of powers of r. Implementation of this idea but time limit exceed.

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

solve ::[Integer]-> BS.ByteString 
solve (a:b:n:m:_) = BS.pack.show $ mod ( powM ( mod a m ) n m + mod ( mod b m * geoSum ( mod a m ) n m ) m ) m 


powM :: Integer -> Integer -> Integer -> Integer 
powM a 0 _ = 1
powM a 1 m = mod a m 
powM a b m = if odd b then mod ( a * powM ( mod ( a^2 ) m ) ( div b 2 ) m ) m else mod ( powM ( mod ( a^2) m  ) ( div b 2 ) m ) m 


geoSum :: Integer -> Integer -> Integer -> Integer
geoSum a 0 _ = 0
geoSum a 1 _ = 1
geoSum a n m = if even n then mod ( ( 1 + powM a ( div n 2 ) m ) * mod ( geoSum a ( div n 2 ) m ) m ) m  
		 else mod ( ( ( 1 + powM a ( div n 2 ) m ) * mod ( geoSum a ( div n 2 ) m ) m ) + powM a ( n - 1 ) m ) m 

readN::BS.ByteString -> Integer
readN xs = case BS.readInteger xs of 
	Just ( t , _ ) -> t 
	Nothing -> error " some thing wrong with parsing "

main = BS.interact $ BS.unlines. map ( solve . map readN . BS.words ) . tail . BS.lines 

My second though was matrix multiplication for linear recurrence relation and finally it worked. F_n can be calculated as \left( \begin{array}{ccc}  a & b \\  0 & 1 \end{array} \right)^n and taking sum of first row elements. Accepted Haskell and first one to solve in Haskell ;).

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


solve::[Integer] -> BS.ByteString 
solve (a:b:n:m:_) = BS.pack.show $ solveH [mod a m ,mod b m , 0 , 1 ] n m 

solveH :: [Integer] -> Integer -> Integer -> Integer
solveH [a,b,0,1] n m = mod ( c+d ) m where 
	[c,d,_,_] = powM [a,b,0,1] n m 

powM :: [Integer] -> Integer -> Integer -> [Integer] 
powM [a,b,c,d] 0 _ = [1,0,0,0]
powM [a,b,c,d] 1 m = [mod a m , mod b m , mod c m , mod d m ]
powM [a,b,c,d] n m = if even n then powM ( mult [a,b,c,d] [a,b,c,d] m ) ( div n 2 ) m 
                      else mult ( powM ( mult [a,b,c,d] [a,b,c,d] m ) ( div n 2 )  m  ) [a,b,c,d] m 

mult :: [Integer] -> [Integer] -> Integer -> [Integer]
mult [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 

readN::BS.ByteString -> Integer
readN xs = case BS.readInteger xs of 
	Just ( t , _ ) -> t 
	Nothing -> error " some thing wrong with parsing "

main = BS.interact $ BS.unlines. map ( solve . map readN . BS.words ) . tail . BS.lines 
Advertisements

June 14, 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: