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  = [l:replicate d  ++ ds]
ptds ds d l x = concat [ptds (n:ds) (d-1) (l-n) $ x-d^2*n |
n <- [..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 $ [..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]