给定 mmm。对于一个 nnn,我们可以算出随机生成 nnn 个 [1,m][1,m][1,m] 的数后,所有的数都被生成过的概率,记为 P(n)P(n)P(n)。如 m=3m=3m=3 时 P(3)=627P(3)=\frac{6}{27}P(3)=276,P(4)=3681P(4)=\frac{36}{81}P(4)=8136。
再给定 p∈(0,1)p\in(0,1)p∈(0,1)。求 nnn 至少为多少,才有 P(n)>pP(n)>pP(n)>p。
根据我的代码跑出来的结果,大概是 O(mlogm)O(m\log m)O(mlogm) 的。能否证明这一点,或者给出更加详细的表达式?