给定一个 nn 个点 mm 条边的无向图,其中每个点的点权是 0;1 范围内生成的连续型随机变量,求:

max { max_{i in V} x_i + max_{(u,v) in E} (x_u + x_v) }
max{
i∈V
max

x
i

  • (u,v)∈E

max

(x
u

+x
v

)}
的期望,答案对 998244353998244353 取模。

n leq 25n≤25。(实际上可以跑 n leq 30n≤30。。。

题解
ans = int_0^2 Pr[lambda = x] x text dx = 2 - int_0^2 Pr[lambda leq x] text dx
ans=∫
0
2

Pr[λ=x]xdx=2−∫
0
2

Pr[λ≤x]dx
考虑如何计算 Pr[lambda leq x]Pr[λ≤x],设 g(s,y,t)g(s,y,t) 表示对于点集 ss,点权最大值 leq y≤y,答案 leq t≤t 的概率。考虑其状态转义:

如果生成的所有数都 leq frac t 2≤
2
t

,则贡献为 (frac t 2)^{|s|}(
2
t

)
∣s∣

对于其他情况,考虑最大值点 ii,并递归。
g(s,y,t) = (tfrac t 2)^{|s|} + sum_{i in s} int_{tfrac t 2}^y g(s_i, x, t) (t - x)^{|s| - |s_i| - 1}text dx
g(s,y,t)=(
2
t

)
∣s∣

  • i∈s




2
t

y

g(s
i

,x,t)(t−x)
∣s∣−∣s
i

∣−1
dx
其中 s_is
i

表示从 ss 中删除 ii 以及所有和 ii 相邻的点得到的点集。

如果我们直接暴力状压维护二元多项式转移显然麻烦的一比,而且常数还贼他妈大,考虑理性一点的方式。

首先,如果当前的状态是若干独立的联通块,可以直接把每个联通块的答案相乘,这可以大大减小状态数。

另外,我们可以注意到,对于二元多项式的每一项 y^i t^jy
i
t
j
,都满足 i+ji+j 是定值,即二元多项式 g(s)g(s) 每项的幂次和都是 |s|∣s∣。由二项式定理的系数可以方便得到。

最后,我们需要注意 g(s,y,t)g(s,y,t) 的取值范围 tfrac t 2 leq y leq min(1, t)
2
t

≤y≤min(1,t),所以答案是

ans = 2 - int_0^1 f(t,t) text dt - int_1^2 f(1,t) text dt
ans=2−∫
0
1

f(t,t)dt−∫
1
2

f(1,t)dt
代码

回顾自己的2020年,发生了很多事,但翻开博客发现2020年只有寥寥几篇博文。
这可能印证了,当自己真的很忙的时候,写博客就会变得不是那么重要,纵然如此,但总是感觉缺少了些什么。
回想过去的2020,有欣喜、有苦楚、有忙碌、有收获。



READ MORE

© 2008 - 2021 winegrower
...... Visitors , 16.22 W Words