Project Euler 76

Problem 76
5は6つの違う方法で和に書ける。
4 + 1
3 + 2
3 + 1 + 1
2 + 2 + 1
2 + 1 + 1 + 1
1 + 1 + 1 + 1 + 1
100を少なくとも2つの和に書く方法は何通りあるか。
http://projecteuler.net/index.php?section=problems&id=76

これは分割数と言われるものです。普通は例えば5なら5だけというのも含まれます。以下それで考えて、最後に1を引きます。
まず、再帰的に考えてnをk以下の数で分割する関数を作ります。これだけだと遅いですが、メモ化をすれば十分に速いです（Code1）。

次に、5を1で分割、2以下で分割、というように順番に考える方法です。これは次の母関数に対応しています。

P(x) = (1 + x + x² + ...)(1 + x² + x⁴ + ...)...(1 + xⁿ + x²ⁿ + ...)

簡単に書けます（Code2）。

実は分割数には簡単な漸化式があります。検索して調べてください。これを使うとProblem 78も簡単です（Code3）。

# Code1
def P(n, k = 0):
    if n < 0:
        return 0
    
    if k == 0 or k > n:
        k = n
    
    if k == 1 or n <= 1:
        return 1
    
    if (n, k) in memo:
        return memo[(n,k)]
    
    s = sum(map(lambda m: P(n - m, m), range(1, k + 1)))
    memo[(n,k)] = s
    return s

N = 100
memo = { }
print P(N) - 1

# Code2
from itertools import imap

def mul(a, m):
    return [ sum(imap(lambda l: a[k-l], xrange(0, k + 1, m)))
                                        for k in xrange(N + 1) ]

N = 100
a = reduce(lambda a, m: mul(a, m), range(2, N + 1), [ 1 ] * (N + 1))
print a[N] - 1

# Code3
from itertools import count

def gen_arg(n):
    sign = 1
    for k in count(1):
        p = n - (3 * k - 1) * k / 2
        q = n - (3 * k + 1) * k / 2
        if q >= 0:
            yield sign * (a[p] + a[q])
        elif p >= 0:
            yield sign * a[p]
        else:
            break
        sign = -sign

def f(n):
    a[n] = sum(gen_arg(n))

N = 100
a = [ 1 ] * (N + 1)
reduce(lambda x, y: f(y), xrange(N + 1))
print a[N] - 1