プロジェクトオイラー
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 Truedef 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 sdef C(n, k):
if k == 0:
return 1
return C(n, k - 1) * (n - k + 1) / kdef 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 adef 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)) % Mdef 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)