http://projecteuler.net/index.php?section=problems&id=76
分割数は母関数を使えば簡単。
n = 100 mul f n = [ g f k 0 | k <- [0..] ] where g (x:xs) k m | k < m = 0 | otherwise = (if mod (k - m) n == 0 then x else 0) + (g xs k (m + 1)) p = foldl mul [1,1..] [2..n] main = print ((p!!n) - 1)
ただし、多項式の積を一般的に書こうとするとけっこう大変だし、やや遅くなる。
n = 100 mul f g = [ sum [ p * q | (p:ps,q:qs) <- e ] | e <- a ] where a = [(f,g)]:[ next e | e <- a ] next [(x:xs,y:ys)] = [(x:xs,ys), (xs,y:ys)] next ((xs,y:ys):a) = (xs,ys):(next a) fs = [ [ if mod k n == 0 then 1 else 0 | k <- [0..] ] | n <- [1..] ] p = foldl mul (1:[0,0..]) (take n fs) main = print ((p!!n) - 1)
