Problem 172

http://projecteuler.net/index.php?section=problems&id=172
流れは前問と似ている。
まず、分割して、その出現回数を数え、和をとる。
久々に一瞬で走る。

import Data.List

divid :: Int -> Int -> Int -> [[Int]]
divid 0 _ k = [replicate k 0]
divid x m k = concat [map (n:).divid (x-n) n $ k-1| n <- [1..m], x - n >= 0, x - k*n <= 0]

count :: [Int] -> Integer
count xs = fact 10 * fact (sum xs) `div` product (map fact $ xs ++ d)
    where d = map length.group $ xs
          fact n = product [1..toInteger n]

p172 :: Int -> Integer
p172 n = (`div` 10).(9*).sum.map count.divid n 3 $ 10