# My Weblog

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