题意
有一段长为 \(l\) 的线段，有 \(n\) 个区间，左右端点在 \([0,l)\) 间均匀随机（可能不是整数）。
求期望被至少 \(k\) 段区间覆盖的长度，对 \(998244353\) 取膜模。
题解
以前完全不会此类期望题目（悲），来记一下做法。
首先 \(l\) 是无用的，算 \([0,1)\) 的答案，结果乘以 \(l\) 即可。
由期望的线性性和积分相关知识，不难发现答案就是：线段上一点 \(x\) 被覆盖至少 \(k\) 次的概率。
概率的套路，考虑将其转化为计数。点被线段覆盖，可以转化为点在另外两个点中间（因为重合的概率极小，所以可以不考虑）。我们发现这只与点之间的相对位置有关。相对位置关系共有 \((2n+1)!\) 种，我们需要算有多少种满足有一点 \(x\) 被覆盖至少 \(k\) 次。
到这里DP已经呼之欲出了。设 \(f_{i,j,0/1}\) 表示选了 \(i\) 个点，有 \(j\) 个左端点没有匹配上，是否已选 \(x\) 的方案数。则：
\[f_{i,j,k}→f_{i+1,j+1,k} \]\[f_{i,j,k} \times j→f_{i+1,j-1,k} \]\[f_{i,j,0}→f_{i+1,j,1}(j \ge k) \]最后方案数为 \(f_{2n+1,0,1} \times 2^n \times n!\)。\(2^n\) 因为左右端点可以互换，\(n!\) 因为线段可以互换。
标签：CF1153F,覆盖,题解,线段,times,端点 From： https://www.cnblogs.com/FishJokes/p/16796112.html