题意:给出一个凸多边形,随机选取其中 $k$ 个点,问其构成的多边形的面积期望是多少.
题解:对于每条有向线段,判断其出现在多边形中的概率,这样就能算出其左边的部分对被删去部分的期望的贡献.统计被删去部分的期望,用面积减去就是答案.
题意:在矩阵中选择任意行任意列,求有多少方案,使得被选中的元素按照原顺序组成的矩阵每行每列都是单调的.
预处理两两行之间没有列的递增递减关系.
对于行的 dp 只考虑 $\ge $ 两行的情况,那么行的顺序已经由前两行固定了,只需要直接按照情况 dp 转移.
Problem F
题意:给定一棵树,每个节点的权值是 $[0b_i]$ 中的随机实数.求这棵树生成一个小顶堆的概率.
需要用 FFT 求多项式模 $10^9+7$ 下的乘积.
Problem G
题解:预处理, $s$ 中每一个位置之后第一个出现的每一个字母的位置,包含 $t$ 的子序列,从每一个位置对应地向后跳即可.
于是枚举 $s$ 的每一个开始位置包含 $t$ 的最前的位置吗,显然从这一位向后都可以作为结束位置,直接统计答案就可以了.