## 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 and wrote a Haskell solution which got TLE but its worth sharing the code because i learned how to calculate sum to geometric series mod without calculating the inverse of m with respect to r. Sum of geometric series will be mod . 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 ) and if n is odd then we have to add the last term to this sum. This way we can calculate the whole sum in O() 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. can be calculated as 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

No comments yet.

## Leave a Reply