Project Euler Problem 015

ans1 :: Integer
ans1 = nckp 40 20
ans2 :: Integer
ans2 = ncki 40 20
-- 137846528820
main :: IO ()
main = print ans1

--haskellではあまり気にせずこんな実装で良い
nckp :: Integral a => a -> a -> a
nckp n k = product [n,n-1..(n-k+1)] `quot` product [1..k]
ncki :: (Enum a, Num a) => Int -> Int -> a
ncki n k = (iterate(scanl1(+))[1,1..]) !! (n-k) !! k

-- ナイーブに実装するならこんな感じ。でも遅くて本問は解けない
nck :: Integral a => a -> a -> a
nck _ 0 = 1
nck n 1 = n
nck n k | n == k = 1
nck n k | n < k = 0
nck n k | k > (n`quot`2) = nck n (n - k)
nck n k = nck (n-1) k + nck (n-1) (k-1)