Project Euler 240 - inamori’s diary

Q240.
12面あるサイコロを20個振って、目の上位10個の和が70になる場合の数はいくつか。

70の10個への分割を生成するジェネレータを作ればよい。重複しないように、降順のものを出し、例えば例にあるような6,5,4なら6倍する。そして、残りは4の2乗、と言いたいところだが、それだと重複するので、6,5,4のあとは3以下、6,5,4,4のあとは3以下、6,5,4,4,4と分ける。気になったのは、0 ** 0の計算が出てくることだが、Pythonでは1になるので、問題なかった。



def C(n, m):

    if m == 0:

        return 1

    

    return C(n, m - 1) * (n - m + 1) / m
def gen_div(n, k, l = 0):

    if k == 1:

        if 1 <= n and n <= l and n <= N:

            yield (n, )

    elif n >= k:

        if l == 0:

            l = N

        

        for m in xrange(1, l + 1):

            for t in gen_div(n - m, k - 1, m):

                yield (m, ) + t
def convert(t):

    t2 = ()

    prev = 0

    for n in t:

        if prev != n:

            if prev == 0:

                counter = 1

            else:

                t2 += (counter, )

                counter = 1

        else:

            counter += 1

        prev = n

    t2 += (counter, )

    return t2
def comb(t, n):

    p = 1

    for e in convert(t):

        p *= C(n, e)

        n -= e

    return p
N = 12

M = 20

L = 70

K = 10
s = 0

for t in gen_div(L, K):

    m = min(t)

    for k in xrange(M - K, -1, -1):

        s += (m - 1) ** k * comb(t, M)

        t = t + (m, )

print s