spoj - Novice63.hs

Novice63.hs

{-# OPTIONS_GHC -O2 -XNoMonomorphismRestriction #-}
{-# LANGUAGE BangPatterns #-}
{-(c) gorlum0 [at] gmail.com-}
import qualified Data.ByteString.Char8 as BS
import Data.Maybe (fromJust)

readNum = fst . fromJust . BS.readInteger
fI = fromIntegral

fact n = product [1..n]
binom n k = (fact n) `div` (fact k) `div` (fact $ n - k)

-- only evens - 0 for odds
specials = [if even n then binom (n-1) k else 0 |
                n <- [1,2..60], let k = n`div`2 - 1]

totalSpecials :: Integer -> Integer
totalSpecials 2 = 1
totalSpecials n = sum $ take m specials
    where m = floor $ logBase 2 (fI n)

main = do
    (l:ls) <- BS.lines `fmap` BS.getContents
    let t = readNum l
        ns = map readNum ls
    mapM_ print [totalSpecials n | n <- ns]