## 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 . can be written as so our recurrence is . Now the only remaining task is to get the matrix form for this recurrence.

.

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 which is equal to the . 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

No comments yet.

## Leave a Reply