💡
原文中文，约1200字，阅读约需3分钟。
📝
内容提要
文章讨论了通过递推和概率计算期望次数 E[i] 的方法，涉及二项分布和动态规划。首先对所有数减一，然后利用 A[i][j] 和 B[i] 计算 E[i]，最终得出 O(n^2) 的复杂度。
🎯
关键要点
- 文章讨论了通过递推和概率计算期望次数 E[i] 的方法。
- 涉及二项分布和动态规划。
- 首先对所有数减一，n 表示进行了 n 个回合。
- 设 E[i] 为最后 i 出现的期望次数。
- E[n] 和 E[0] 的计算相对简单。
- E[n-1] 和 E[n-2] 需要更深入的讨论。
- 需要枚举第一次出现 i 的时刻，设 A[i][j] 为 i 第一次出现在 j 时刻的概率。
- E[i] 的计算公式为 E[i] = A[i][j] B[n-j]，其中 j 从 0 到 n。
- B[i] 表示当前最高位后续再进行 i 个回合期望出现的次数。
- A[i][j] 的计算涉及二项分布，公式为 A[i][j] = C(j-1, i-1) p^i (1-p)^(j-i)。
- B[i] 的递推关系为 B[0] = 1 和 B[i] = B[i-1] + B[i-1] / (n-i)。
- 最终得出 O(n^2) 的复杂度。
- 提供了相关的代码实现，使用动态规划和组合数学计算 E[i]。
❓
延伸问答
如何通过递推和概率计算期望次数 E[i]？
通过设定 E[i] 为最后 i 出现的期望次数，并利用 A[i][j] 和 B[n-j] 的关系进行计算。
A[i][j] 和 B[i] 在计算中有什么作用？
A[i][j] 表示 i 第一次出现在 j 时刻的概率，B[i] 表示当前最高位后续再进行 i 个回合期望出现的次数。
E[n] 和 E[0] 的计算有什么特点？
E[n] 和 E[0] 的计算相对简单，E[n] 是每次都 p，E[0] 只与当前有多少个 0 有关。
如何计算 A[i][j] 的值？
A[i][j] 的计算公式为 A[i][j] = C(j-1, i-1) p^i (1-p)^(j-i)，涉及二项分布。
B[i] 的递推关系是什么？
B[i] 的递推关系为 B[0] = 1 和 B[i] = B[i-1] + B[i-1] / (n-i)。
这篇文章的复杂度是多少？
最终得出的复杂度为 O(n^2)。
➡️
