240 Top Dice

Problem 240 – Project Euler

さいころの問題．組み合わせの数をもとめる．

ふつうに，上位10個の和が70になるようなやつをもとめ，残りの並べかたなどを考慮． 

topSum :: (Integral a) => a -> a -> a -> a -> [[(a, a)]]
topSum f n m s
| s <      = []
| m == f    = if s == m * n then [[(m, n)]] else []
| otherwise = topSum f n (m + 1) s ++ concat [ map ((m, k):) $ topSum f (n - k) (m + 1) (s - k * m) | k <- [1..n] ]
where u_k = div ( n * f - s ) (f - m)
count :: (Integral a) => a -> a -> [(a, a)] -> a
count t r ((m, n):ns) = sum [ fact t * (m - 1) ^ (r - k) `div` (fact (n + k) * fact (r - k) * d) | k <- [..r] ]
where d = product.map (fact.snd) $ ns
fact :: (Num a, Enum a) => a -> a
fact n = product [1..n]
p240 :: (Integral a) => a -> a -> a -> a -> a
p240 f t n = sum.map ( count t (t - n)).topSum f n 1
main :: IO ()
main = print $ p240 12 20 10 70