Skip to content

Instantly share code, notes, and snippets.

@roman
Last active February 5, 2017 00:13
Show Gist options
  • Save roman/42da80d9e113beb944dd46f230bb775b to your computer and use it in GitHub Desktop.
Save roman/42da80d9e113beb944dd46f230bb775b to your computer and use it in GitHub Desktop.
module Main where
import Control.Applicative
import Control.Monad
import Data.List (foldl')
import qualified Data.Sequence as Seq
import qualified Data.Vector (freeze)
import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Unboxed.Mutable as VM
--------------------------------------------------------------------------------
-- Queue Implementation
type Queue a = Seq.Seq a
emptyQueue = Seq.empty
enqueue a queue = a Seq.<| queue
dequeue queue =
case Seq.viewl queue of
Seq.EmptyL ->
Nothing
a Seq.:< queue1 ->
Just (a, queue1)
nullQueue = Seq.null
--------------------------------------------------------------------------------
-- permutations :: Int -> Int -> Int
-- permutations n k =
-- let
-- step acc i =
-- acc * (n - i)
-- in
-- foldl' step n [1..(k - 1)]
combinations n k =
let
diff =
n - k
nominator =
product [succ (max diff k) .. n]
denominator =
product [1..(min diff k)]
in
nominator `div` denominator
main :: IO ()
main = do
testCases <- readLn
replicateM_ testCases $ do
(n:k:[]) <- map read . words <$> getLine
print $ combinations n k `mod` ((10^8) + 1)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment