C/C++教程

省内联考 10.17 随机过程(process)

本文主要是介绍省内联考 10.17 随机过程(process),对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

简要题意:

在长度为 \(l\) 的数轴上均匀随机 \(n\) 个区间,求被至少 \(k\) 个区间覆盖的长度期望。

这个描述已经足够形式化了,下面直接开始推导。

设 P_x 为每个点合法的概率,二项式反演有:

$$P_x=\sum_{i=k}^n\binom{n}{i}(2x(1-x))^i(1-2x(1-x))^{n-i}$$

枚举 \(k\),则

$$answer =\int_0^1\sum_{i=k}^n\binom{n}{i}(2x(1-x))^i(1-2x(1-x))^{n-i}dx$$

提出组合数,交换求和顺序,得到

$$answer =\sum_{i=k}^n\binom{n}{i}\sum_{j=0}^{n-i}(-1)^j\binom{n-i}{j}2^{i+j}\int_0^1x^{i+j}(1-x)^{i+j}dx$$

接着我们发现后面是一个 \(\text{Beta}\) 积分,代入定义:

$$answer =\sum_{i=k}^n\binom{n}{i}\sum_{j=0}^{n-i}(-1)^j\binom{n-i}{j}2^{i+j} \text{B}(i+j+1,i+j+1)$$

展开二项式系数,转化为差卷积形式,结合 \(\text{NTT}\) 可以做到 \(O(n \log n)\)。

Elegia 教导我,fix 一下 \(i,j\),我们考虑组合恒等式:

$$\sum_{j=0}^{i-k}(-1)^j\binom{i}{j}=(-1)^{i-k}\binom{i-1}{i-k}$$

枚举 \(i + j\),此时瓶颈变为了二项式系数求和,代入并交换求和顺序得到:

$$answer=\sum_{i=k}^n(-1)^{i-k}\binom{i-1}{i-k}\binom{n}{i}2^iB(i+1,i+1)$$

至此,我们以 \(O(n)\) 的时间复杂度解决了这个问题。

Upd:上文的组合恒等式可以视作平行求和的逆过程,至于有什么组合意义还待讨论

这篇关于省内联考 10.17 随机过程(process)的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!