「nowcoder 271C」左方之地-概率期望

发布于 11 天前  27 次阅读


本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「nowcoder 271C」左方之地-概率期望

Description

左方之地是全宇宙最帅的男人,由于有人嫉妒他的帅气,他决定出一道题考一考这些嫉妒他帅气的人。

左方之地现在手上有$n$件不同的灵装,第$i$件灵装有一个帅气值$a_i$ ,现在他将灵装随机摆成一个排列,并将这个排列映射到一棵二叉树上,这棵二叉树的中序遍历是原排列,且每一个节点上的灵装编号都要小于其子树中的所有点的灵装编号。可以证明对于一个排列,这样的二叉树的形态是唯一的。

这棵树会产生一个总的帅气值等价于树上每个节点的灵装的帅气值乘上该节点的深度(根节点的深度为$1$)之和,左方之地想让你求出期望能获得的总帅气值在膜$998244353$意义下的结果是多少

Solution

题意可以转化为对$1-n$随机排列,以原排列为$key$,随机后的排列为$value$的笛卡尔树上的深度乘权值的期望。根据期望的线性性:

$$dep_i=\sum_j[j \ \ is \ \ an \ \ ancestor \ \ of \ \ i]$$

设随机后的排列为$p$,考虑在笛卡尔树$i$为$j$的祖先当且仅当$p_i$是区间$[i,j]$中是最小的元素。反过来考虑即$i$是区间$[p_i,p_j]$中是最小的元素。只考虑不大于$i$小的元素,先插入比$i$小的元素再插入$i$和$j$。由于只有$i+1$个空位,所以概率是$\frac{2}{i+1}$。所以

$$ ans=\sum a_i + \frac {2} {i+1} \sum_{j>i} a_j $

本文章由SYCstudio或本站其它作者所有,请勿擅自转载

本文链接地址:「nowcoder 271C」左方之地-概率期望


或许前方只有...伸手不见五指的夜路,即使如此,我还是要充满信心、继续向前, 相信星星的光芒...多少会照亮前方的道路,走吧!我们踏上旅程吧!