← 完整题目索引

PROJECT EULER · #0666

多态性细菌

Polymorphic Bacteria

仅题目 · 待解原题 ↗
一种细菌的成员有两种不同的类型:αβ。单个细菌能够根据以下规则在不同类型之间繁殖和突变:
  • 每一分钟,每个人都会同时经历某种转变。
  • α 类型的每个个体 A 将独立地执行以下操作之一(以相等的概率随机):
    • 克隆自身,产生 α 类型的新细菌(与剩下的 A 一起)
    • 分裂成 3 个 β 类型的新细菌(取代 A
  • β 类型的每个个体 B 将独立地执行以下操作之一(以相等的概率随机):
    • 产生 α 类型的新细菌(与剩下的 B 一起)

如果一个种群以 α 类型的单个细菌开始,那么可以证明,该种群最终灭绝的概率为 0.07243802,而该种群将永远存在的概率为 0.92756198。这些概率四舍五入到小数点后 8 位。

现在考虑另一种细菌,Sk,m(其中km是正整数),它出现在k不同类型αi中,0i<k。管理该物种生命周期的规则涉及序列 rn,定义如下:

  • r0=306
  • rn+1=rn2mod10007

每分钟,对于每个iαi类型的每个细菌A都会在0j<m范围内独立、均匀地随机选择一个整数j。然后它做什么取决于 q=rim+jmod5:

  • 如果 q=0A 就会死亡。
  • 如果 q=1A 会克隆自身,从而产生 αi 类型的新细菌(与剩下的 A 一起)。
  • 如果 q=2A 会发生变异,变为 α(2i)modk 类型。
  • 如果 q=3A 分裂成 3 个类型为 α(i2+1)modk 的新细菌(取代 A)。
  • 如果 q=4A 会产生 α(i+1)modk 类型的新细菌(与剩下的 A 一起)。

事实上,我们的原始物种正是S2,2,其中α=α0β=α1

Pk,m 为物种 Sk,m 的种群,从 α0 类型的单个细菌开始,最终灭绝的概率。所以 P2,2=0.07243802。您还可以得到 P4,3=0.18554021P10,5=0.53466253,全部四舍五入到小数点后 8 位。

找到 P500,10,并将答案四舍五入到小数点后 8 位。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。