CF1153F Solution
题意:
有一段长为 \(l\) 的线段,有 \(n\) 个实数区间,左右端点在 \([0,l)\) 间均匀随机。
求期望被至少 \(k\) 段区间覆盖的长度,对 \(998244353\) 取模。
\(1\le k\le n\le 10^7,1\le l \le 10^{10^6}\)
首先 \(l\) 是没用的,我们可以计算线段长为 \(1\) 时的答案最后乘上一个 \(l\)。
考虑到区间是实数区间,期望等于概率乘值,那么答案等于
\[\int_{0}^1f(x)dx \]\(f(x)\) 表示线段上点 \(x\) 被至少 \(k\) 个区间覆盖的概率。那么根据定义
\[f(x)=\sum_{i=k}^n\binom n i(2x(1-x))^i(1-2x(1-x))^{n-i} \]所求即为
\[\begin{aligned} \int_{0}^1f(x)dx &=\int_{0}^1\sum_{i=k}^n\binom n i(2x(1-x))^i(1-2x(1-x))^{n-i}dx\\ &=\int_{0}^1\sum_{i=k}^n\binom n i(2x(1-x))^i\sum_{j=0}^{n-i}\binom {n-i}j(-2x(1-x))^jdx\\ &=\int_{0}^1\sum_{i=k}^n\sum_{j=0}^{n-i}\binom n i\binom {n-i}j(-1)^j(2x(1-x))^{i+j}dx\\ &=\int_{0}^1\sum_{i=k}^n\sum_{j=0}^{n-i}\frac{n!}{i!(n-i)!}\frac{(n-i)!}{j!(n-i-j)!}(-1)^j(2x(1-x))^{i+j}dx\\ &=\int_{0}^1\sum_{i=k}^n\sum_{j=0}^{n-i}\frac{n!(i+j)!}{i!j!(n-i-j)!(i+j)!}(-1)^j(2x(1-x))^{i+j}dx\\ &=\int_{0}^1\sum_{i=k}^n\sum_{j=0}^{n-i}\binom n{i+j}\binom{i+j}j(-1)^j(2x(1-x))^{i+j}dx\\ \end{aligned}\]枚举 \(s=i+j\)
\[\begin{aligned} \int_{0}^1f(x)dx &=\int_{0}^1\sum_{s=k}^n\sum_{j=0}^{s-k}\binom n s\binom s j(-1)^j(2x(1-x))^sdx\\ &=\int_{0}^1\sum_{s=k}^n\binom n s2^s(x(1-x))^s\sum_{j=0}^{s-k}\binom s j (-1)^jdx\\ &=\sum_{s=k}^n\binom n s2^s\int_{0}^1x^s(1-x)^sdx\sum_{j=0}^{s-k}\binom s j (-1)^j\\ \end{aligned}\]注意到中间这个积分,这玩意是 Beta 函数,可以直接套通项。但是我不会,那只能自己推一推。
\[\begin{aligned} \int_{0}^1x^s(1-x)^sdx &=\int_{0}^1\left(\sum_{i=0}^s\binom s i(-1)^ix^{i+s}\right)dx\\ &=\sum_{i=0}^s\binom s i(-1)^i\frac{x^{i+s+1}}{i+s+1}\Big|_0^1\\ &=\color{red}\sum_{i=0}^s\binom s i(-1)^i\frac1{i+s+1}\\ &=\sum_{i=0}^s\left(\binom {s-1} i+\binom{s-1}{i-1}\right)(-1)^i\frac 1{i+s+1}\\ &=\sum_{i=0}^{s-1}\binom {s-1} i(-1)^i\frac 1{i+s+1}-\sum_{i=0}^{s-1}\binom {s-1} i(-1)^i\frac 1{i+s+2}\\ &=\color{red}\sum_{i=0}^{s-1}\binom {s-1} i(-1)^i\frac 1{(i+s+1)^{\overline2}}\\ &=\sum_{i=0}^{s-1}\left(\binom{s-2}i+\binom{s-2}{i-1}\right)(-1)^i\frac 1{(i+s+1)^{\overline2}}\\ &=\sum_{i=0}^{s-2}\binom {s-2} i(-1)^i\frac 1{(i+s+1)^{\overline2}}-\sum_{i=0}^{s-2}\binom {s-2}{i}(-1)^i\frac 1{(i+s+2)^{\overline2}}\\ &=\color{red}\sum_{i=0}^{s-2}\binom {s-2} i(-1)^i\frac {2}{(i+s+1)^{\overline3}}\\ \end{aligned}\]到这里,可以猜测(归纳证明)这个式子一直推下去会长成类似这个样子
\[\sum_{i=0}^{s-k}\binom {s-k} i(-1)^i\frac {k!}{(i+s+1)^{\overline{k+1}}} \]那么到最后它就是
\[\begin{aligned} \sum_{i=0}^{s-s}\binom {s-s} i(-1)^i\frac {s!}{(i+s+1)^{\overline{s+1}}} &=\frac{s!}{(s+1)^{\overline{s+1}}}\\ &=\frac{(s!)^2}{(2s+1)!}\\ \end{aligned}\]代回原式,
\[\begin{aligned} \int_{0}^1f(x)dx &=\sum_{s=k}^n\binom n s2^s\frac{(s!)^2}{(2s+1)!}\sum_{j=0}^{s-k}\binom s j (-1)^j\\ &=\sum_{s=k}^n\binom n s2^s\frac{(s!)^2}{(2s+1)!}\sum_{j=0}^{s-k}\left(\binom{s-1}j+\binom{s-1}{j-1}\right)(-1)^j\\ &=\sum_{s=k}^n\binom n s2^s\frac{(s!)^2}{(2s+1)!}\left(\sum_{j=0}^{s-k}\binom{s-1}j(-1)^j-\sum_{j=0}^{s-k-1}\binom{s-1}j(-1)^j\right)\\ &=\sum_{s=k}^n\binom n s2^s\frac{(s!)^2}{(2s+1)!}\binom{s-1}{s-k}(-1)^{s-k}\\ \end{aligned}\]\(\mathcal O(n)\) 直接计算即可。
标签:frac,dx,int,sum,2x,solution,cf1153f,binom From: https://www.cnblogs.com/iorit/p/18037983