UOJ

思路

由于最近养成的不写代码的习惯(其实就是懒),以下式子不保证正确性。

上来我们先甩一个min-max容斥。由于每只鸽子是一样的,这只贡献了\(O(n)\)的复杂度。

现在的问题转化为对于\(n\)只鸽子里面的\(c\)只鸽子,求喂饱其中一只鸽子的期望时间。

我们对期望的式子差分一下,变成统计经过\(i\)秒之后\(c\)只鸽子仍然一只都没有被喂饱的概率。

枚举这\(i\)秒里面有\(s\)秒喂到了,设\(f_{c,s}\)表示给\(c\)只鸽子喂了\(s\)粒玉米,一只都没有饱的概率,我们得到
\[
ans_c=\sum_i \sum_{s=0}^i {i\choose s} (\frac {n-c} n)^{i-s}f_{c,s}
\]
(上式的\((\frac{c}{n})^s\)被塞进\(f_{c,s}\)里面了)

由于\(s> c(k-1)\)的时候\(f\)必然为0,所以可以得到
\[
ans_c=\sum_{s=0}^{c(k-1)} f_{c,s} \sum_i {i+s\choose s} (\frac{n-c}{n})^i
\]
后面那一项很像\(\frac 1 {(1-x)^{s+1}}\)的展开式,可以快速得到,所以问题就转化为求\(f_{c,s}\)。

我们有一个暴力DP的式子:
\[
f_{c,s}=\sum_{i<k} f_{c-1,s-i}{s\choose i} \frac 1 {n^i}
\]
显然可以转换成卷积的形式用NTT优化,最后总复杂度\(O(n^2k\log k)\)。

我们还有另一种做法。把概率变成方案数,我们设\(f_{c,s}\)表示给\(c\)只鸽子喂了\(s\)粒玉米,一只都没有饱的方案数。再设\(f_c(x)\)表示这个东西的指数生成函数。

容易发现,求\(f_c(x)\)其实就等价于求\((\sum_{i=0}^k \frac{x^i}{i!})^c\)。

然后是一个神奇操作:

UOJ449. 【集训队作业2018】喂鸽子 [概率期望,min-max容斥,生成函数]-LMLPHP

(orz daklqw

(daklqw说是从yhx-12243那里学的,所以两个都要orzorz)

于是就\(O(n^2k)\)做完了。

代码

咕咕咕

05-11 22:07