Problem 171

http://projecteuler.net/index.php?section=problems&id=171
数字の出てくる順番は本質的ではない。
平方数を1^2,2^2,3^2,..9^2を使って分割。
その分割からできる数字の和を考える（permutations）。
総和をとる。

digit :: Int
digit = 20

partitionToSquares :: Int -> [[Int]]
partitionToSquares = ptds [] 9 digit
    where ptds ds d l 0 = [l:replicate d 0 ++ ds]
          ptds ds d l x = concat [ptds (n:ds) (d-1) (l-n) $ x-d^2*n |
                                  n <- [0..l], d^2*n <= x && d^2*n+(d-1)^2*(l-n) >= x]
 
sumDigits :: [Int] -> Integer
sumDigits xs = div (m*s*fact (digit-1)).product.map fact $ xs
    where s = toInteger.sum.zipWith (*) xs $ [0..9]
          m = foldl1 (\a b -> 10*a+b).replicate digit $ 1
          fact n = product.map toInteger $ [1..n]

main :: IO ()
main = print.(`mod` (10^9)).sum.map sumDigits.concatMap partitionToSquares $ ss
    where ss = map (^2) [1..floor.sqrt.fromIntegral $ digit*9^2]