Submission #188254

---

Source Code Expand

{-# LANGUAGE CPP #-}
#ifndef HDEVTOOLS
{-# OPTIONS_GHC -O2 -funbox-strict-fields #-}
#endif
{-# LANGUAGE BangPatterns, ViewPatterns, OverloadedStrings #-}

import Control.Applicative
import Control.Monad
import Data.Maybe
import qualified Data.ByteString.Char8 as S
import qualified Data.Vector as V

main :: IO ()
main = do
  [n, d] <- map readInt . S.words <$> S.getLine
  [x, y] <- map readInt . S.words <$> S.getLine
  print $ solve n d x y

solve :: Int -> Int -> Int -> Int -> Double
solve n d x y = fromMaybe 0 $ do
  (x', 0) <- return $ divMod x d
  (y', 0) <- return $ divMod y d
  guard $ abs x' + abs y' <= n
  return $! solveSimple n x' y'

solveSimple :: Int -> Int -> Int -> Double
solveSimple n x y = realToFrac $
  (fromIntegral (count n x y) / (4^n) :: Rational)

count :: Int -> Int -> Int -> Integer
count n x y = sum $ do
  u <- [0 .. n]
  let !d = u - x
  guard $ d >= 0
  let !remaining = n - u - d
  guard $ remaining >= 0
  (r, 0) <- return $ divMod (y + remaining) 2
  guard $ r >= 0
  let !l = r - y
  guard $ l >= 0
  return $ fact n `div` fact u `div` fact d `div` fact l `div` fact r

fact :: Int -> Integer
fact k = factTable V.! k

factTable :: V.Vector Integer
factTable = V.scanl (*) 1 $ V.enumFromN 1 1001

readInt :: S.ByteString -> Int
readInt s = case S.readInt s of
  Just (r, "") -> r
  _ -> error $ "not an integer: " ++ show s

Submission Info

Judge Result