Project Euler 194

プロジェクトオイラー
http://projecteuler.net/index.php

Q194.
省略

まず、単体のAとBの取りうる色のパターンの数を数えた。ここに時間がかかっているが、手抜きで特に工夫はしていない。グラフを作ってしらみつぶしに調べている。使う色の数ごとに求めて、そこから本当に使っている色の数に対応するパターンの数を求めている。例えば、4色で計算しても3色しか使っていないものがあるので、それは除いた数の配列も作っておく。それが求まっていると、色の数が大きいときのパターン数が簡単に求められる。あとは漸化式で。

def is_match(i, c, g, a):

    for k in g[i]:

        if k < i and a[k] == c:

            return False

    return True
def num_pattern(g, n, i = 0, a = [ ]):

    if i == len(g):

        return 1

    

    s = 0

    for c in range(n):

        if is_match(i, c, g, a):

            s += num_pattern(g, n, i + 1, a + [ c ])

    return s
def C(n, k):

    if k == 0:

        return 1

    return C(n, k - 1) * (n - k + 1) / k
def calc_pattern(g):

    b = [ ]

    for k in range(len(g) + 1):

        b.append(num_pattern(g, k))

    return b

    

def calc_proper_pattern(b):

    a = [ ]

    for k in range(len(b)):

        s = b[k]

        for l in range(k):

            s -= C(k, l) * a[l]

        a.append(s)

    return a
def add1(c):

    return add(c, a1, a2)
def add2(c):

    return add(c, a2, b2)
def add(c, a, b):

    if c <= 7:

        return b[c] / (c * (c - 1))

    else:

        n = 0

        for k in range(8):

            n += a[k] * C(c, k)

        return n / (c * (c - 1)) % M
def N(a, b, c):

    N1 = [ ]

    a1 = add1(c)

    a2 = add2(c)

    

    for k in range(a + 1):

        N1.append([ ])

        for l in range(b + 1):

            n = 0

            if k:

                n += N1[k-1][l] * a1

            if l:

                n += N1[k][l-1] * a2

            elif k == 0:

                n = c * (c - 1)

            N1[k].append(n % M)

    return N1[a][b]
M = 10 ** 8
g1 = [

    [ 1, 2, 5 ], [ 0, 4, 6 ], [ 0, 3, 5 ], [ 2, 4 ],

    [ 1, 3, 6 ], [ 0, 2, 6 ], [ 1, 4, 5 ]

]

g2 = [

    [ 1, 2, 5 ], [ 0, 4    ], [ 0, 3, 5 ], [ 2, 4 ],

    [ 1, 3, 6 ], [ 0, 2, 6 ], [    4, 5 ]

]
b1 = calc_pattern(g1)

b2 = calc_pattern(g2)

a1 = calc_proper_pattern(b1)

a2 = calc_proper_pattern(b2)

print N(25, 75, 1984)