# My Weblog

## 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.