Project Euler 239

发表于 2022-07-04 更新于 2023-07-03 分类于 Project Euler 阅读次数： 89 本文字数： 1.2k 阅读时长 ≈ 1 分钟

Project Euler 239

题目

Twenty-two Foolish Primes

A set of disks numbered $1$ through $100$ are placed in a line in random order.

What is the probability that we have a partial derangement such that exactly $22$ prime number discs are found away from their natural positions? (Any number of non-prime disks may also be found in or out of their natural positions.)

Give your answer rounded to $12$ places behind the decimal point in the form $0. a b c d e f g h i j k l$ .

解决方案

令 $N = 100, O = 22$ ，并且 $N$ 以内一共有 $M = 25$ 个质数。

不难以下两个过程是独立的：

从 $M$ 个质数中选择 $M - O$ 个，将它们放在原地，一共有 $(\binom{M}{O})$ 种方法。之后便不考虑这 $M - O$ 个质数。
这 $O$ 个质数不应该在原地，但是剩下的 $N - M$ 个非质数则随便排列。

考虑使用动态规划的思想解决第二个步骤的问题。令 $f (i, j) (0 \leq j \leq i)$ 表示有多少个长度为 $i$ 的排列 $p_{1}, p_{2}, p_{3}, \dots, p_{i - 1}, p_{i}$ ，对于特定的 $j$ 个两两不同下标 $a_{1}, a_{2}, \dots, a_{j}$ （注意些下标是可以随意假设的，这里你可以假设成 $a_{i} = i$ ），满足 $p_{a_{1}} \neq a_{1}, p_{a_{2}} \neq a_{2}, \dots, p_{a_{j}} \neq a_{j}$ . 那么可以写出如下状态转移方程：

$f (i, j) = {\begin{aligned} i! & if j = 0 \\ f (i, j - 1) - f (i - 1, j - 1) & else \end{aligned}$

对于方程最后一行， $f (i - 1, j - 1)$ 中的每个排列 $p_{1}, p_{2}, \dots, p_{i - 1}$ ，都可以映射到 $f (i, j - 1)$ 中的 $p_{1}, p_{2}, \dots, p_{i - 1}, \underset{―}{i}$ 。在 $f (i - 1, j - 1)$ 中的 $j - 1$ 个特定下标中，如果再加上一个 $a_{j} = i$ ，那么就相当于在 $f (i, j - 1)$ 中去掉被 $f (i - 1, j - 1)$ 映射出来的排列，剩下的就成为 $f (i, j)$ 中的排列。

合并两个步骤，最终题目的答案为 $\frac{(\binom{M}{O}) \cdot f (N - M + O, O)}{N!}$ .

代码

from tools import C

N = 100
M = 25
O = 22

fac = [1]
for i in range(1, N + 1):
    fac.append(fac[-1] * i)
f = [[0 for x in range(y + 1)] for y in range(N + 1)]  # A047920
for i in range(N + 1):
    f[i][0] = fac[i]
    for j in range(1, i + 1):
        f[i][j] = f[i][j - 1] - f[i - 1][j - 1]
ans = C(M, O) * f[N - (M - O)][O] / fac[N]
print("{:.12f}".format(ans))