LOJ565 [LR10] mathematican 的二进制

Description 一个初始为 0 的二进制数,有 $m$ 次操作。 第 $i$ 次操作是将这个二进制数加上 $2^{a_i}$ 。这个操作以 $p_i$ 的概率执行。 如果某次操作执行了并且修改了二进制数的 $k$ 位,那么它会带来 $k$ 的代价。 问代价和的期望,答案对 $998244353$ 取模。 $n=\max a_i\leqslant10^5, m\leqslant2\times10^5$ ...

BZOJ3925 [ZJOI2015] 地震后的幻想乡

Description 一个 $n$ 个结点、 $m$ 条边的无向图,所有边权在 $[0, 1]$ 之间均匀分布(互相独立);求这个图的最小生成树上的最大边权的期望值。 $n \leqslant 8, m \leqslant \frac{n(n-1)}2$ 。 ...

BZOJ2337 [HNOI2011] XOR和路径

Description $n$个点的无向图,从$1$号点出发每次从所有相连的边随机选一个走过去,直到$n$号点结束。求路径上所有边权异或和的期望。$n\leqslant100, m\leqslant10000$,可能有重边自环。 ...

BZOJ3143 [HNOI2013] 游走

Description 一个$n$个点的图,从$1$开始每次随机选择相邻的边走过去直到走到$n$为止。 现在你要对$m$条边重新从$1$到$m$标号,使得路径上期望边权和最小。问最小值。 ...