Luogu6630 [ZJOI2020] 传统艺能

题意：对一棵 的线段树等随机进行 次区间覆盖（在 个区间中等概率随机），问最终产生的有标记节点的期望个数。

，，时限 。

---

还是按照《Luogu6630 [ZJOI2020] 传统艺能》的套路，分五种颜色讨论，并沿用它的 。

对线段树上的每个点，分别计算其在一次操作中成为五种颜色的点的概率，然后乘上对应转移就得到转移矩阵， 次方即可。

具体地，区间 （父节点为 ）在一次随机操作中成为五类点的概率如下 ：

• 浅灰：询问区间完全包含父亲。

• 黄：询问区间与父亲无交。

• 白：当且仅当与询问区间部分相交。

• 深灰：询问区间完全包含自己，且父亲与询问区间部分相交。

  不妨设 ，则概率为

• 橙：询问区间与自己无交，且父亲与询问区间部分相交。

  不妨设 ，则概率为

复杂度 ，带一个矩阵快速幂的大常数。