脚本宝典收集整理的这篇文章主要介绍了省内联考 10.17 随机过程（process），脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
简要题意：
在长度为 (l) 的数轴上均匀随机 (n) 个区间，求被至少 (k) 个区间覆盖的长度期望。
这个描述已经足够形式化了，下面直接开始推导。
设 P_x 为每个点合法的概率，二项式反演有：
$$P_x=sum_{i=k}^nbinom{n}{i}(2x(1-x))^i(1-2x(1-x))^{n-i}$$
枚举 (k)，则
$$answer =int_0^1sum_{i=k}^nbinom{n}{i}(2x(1-x))^i(1-2x(1-x))^{n-i}dx$$
提出组合数，交换求和顺序，得到
$$answer =sum_{i=k}^nbinom{n}{i}sum_{j=0}^{n-i}(-1)^jbinom{n-i}{j}2^{i+j}int_0^1x^{i+j}(1-x)^{i+j}dx$$
接着我们发现后面是一个 (text{Beta}) 积分，代入定义：
$$answer =sum_{i=k}^nbinom{n}{i}sum_{j=0}^{n-i}(-1)^jbinom{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)^jbinom{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)) 的@R_689_1304@解决了这个问题。
Upd：上文的组合恒等式可以视作平行求和的逆过程，至于有什么组合意义还待讨论
以上是脚本宝典为你收集整理的省内联考 10.17 随机过程（process）全部内容，希望文章能够帮你解决省内联考 10.17 随机过程（process）所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。