Project Euler 239 - inamori’s diary

Q239.
1から100までの番号を振ったディスクをランダムに並べる。素数のディスクがちょうど22個本来の位置と違う確率を求めよ。

どうやっても解ける気がする。美しくなくてもいいから、とにかく漸化式に持ち込む。
置換の数は100!ある。そのうち特定の25個のうち3個だけ不動点がある置換の数を数える。3個の素数を選んで固定する。残り22個の素数のうちn個は非素数へ写されるとする。そうすると、n個の非素数が素数に写される。ある数の置換で、決まったn個以外は不動点がないものの数を数える。それを漸化式にすると、不動点を考えなくてもいいものと、不動点がないものの個数に帰着される。不動点を考えなくてもいいものは簡単。不動点が無いものの個数を数える。置換は、不動点が無いもの、不動点が1個のもの…、と分類できるので、簡単に漸化式を作れる。



from math import factorial
def C(n, m):

    if m == 0:

        return 1

    

    return C(n, m - 1) * (n - m + 1) / m
def P(n, m):

    if m == 0:

        return 1

    

    return P(n, m - 1) * (n - m + 1)
N = 22

M = 25

L = 100

S = [ [ 1 ] ]

for n in range(1, N + 1):

    s = factorial(n)

    for m in range(n):

        s -= C(n, m) * S[m][0]

    S.append([ s ])

    

    for m in range(1, n):

        s = 0

        for k in range(min(m, n - m) + 1):

            s += C(m, k) * P(m, m - k) * P(n - m, k) * S[n-m][k]

        S[n].append(s)

    S[n].append(factorial(n))
s = 0

for n in range(N + 1):

    s += C(N, n) * C(L - M, n) * S[N][n]

p = float(s * C(M, N)) / (factorial(L) / factorial(L - M))

print "%.12f" % p