几度风雨几度春秋 风霜雪雨博激流
历尽苦难痴心不改 少年壮志不言愁

这个博客可能要永远咕咕咕了。

upd:公开了一些之前写过的有意思的题,不对的地方欢迎大佬批评指正。

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

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

的期望,答案对 998244353 取模。

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

READ MORE

定义两个简单无向图 G_{1} =( V_{1} ,E_{1}) ,G_{2} =( V_{2} ,E_{2}) 的乘积为一个新的图 G_{1} \times G_{2} =\left( V^{*} ,E^{*} \right)

其中新的点集 V^{*} 为:

V^{*} = \left\{{(a,b)| a \in V_{1}, b \in V_{2}}\right\}

其中新的边集 E^{*} 为:

E^{*} =\left\{\left(( u_{1} ,v_{1}) ,( u_{2} ,v_{2})\right) \mid ( u_{1} ,u_{2}) \in E_{1}, ( v_{1} ,v_{2}) \in E_{2}\right\}

对于正整数 n,以及给定的图 G_{1} ,G_{2} ,\dotsc ,G_{n},两只鞋太太的家可以表示成

H = (((G_1 \times G_2) \times G_3) \times \cdots) \times G_n

每个 G_k 中任意两点间都有 \frac12 的概率连边,求 H 的连通块的期望。显然 G_k 的全体取法共有 {\large {2^{\binom{m_1}2 + \binom{m_2}2 + \cdots + \binom{m_n}2}}} 种。

方便起见,你只需要输出答案乘以 {\large {2^{\binom{m_1}2 + \binom{m_2}2 + \cdots + \binom{m_n}2}}},对 998244353 取模即可。

1\le n, m_k\le 10^5

READ MORE

给定三张 n 个点的图,生成一张 n \times n \times n 的新图,每个点标号为 \langle i,j,k \rangle。按照以下方式从原图生成:

  • 对于第一张图的每条边 (u,v),和 [1,n] 范围内的 i,j,连边 (\langle u,i,j \rangle, \langle v,i,j \rangle)
  • 对于第二张图的每条边 (u,v),和 [1,n] 范围内的 i,j,连边 (\langle i,u,j \rangle, \langle i,v,j \rangle)
  • 对于第三张图的每条边 (u,v),和 [1,n] 范围内的 i,j,连边 (\langle i,j,u \rangle, \langle i,j,v \rangle)

点有点权 10^{18 (i+j+k)},求新图最大权独立集,对 998244353 取模。

n \leq 10^5

READ MORE

餐馆有 n 张桌子,第 i 张可以坐 c_i 个人。

t 组人来餐馆吃饭,每组的人数是 1g 的均匀随机整数,他们会选择当前空余且可用的桌子中最小的那个。如果没有桌子可以选择,他们就会离开。

问餐馆期望人数,答案保留实数输出。

n \leq 100,\ c_i,g \leq 200,\ t \leq 100

READ MORE

给定一个 n 个点 m 条边的无向图,边已经被黑白染色。要求通过以下操作在 m-1 次内将边全部染成白色。

  • 选定一个简单环,将环边的反转颜色
  • 将图黑白染色,将端点异色的边反转颜色

判断是否可行。

n \leq 300,\ m \leq \frac {m(m-1)} 2

READ MORE

n 个桶,每个桶的容量上限是 a,需求量是 b,每次可以随机一个没有达到容量上限的桶加注 1 单位目标液体,当所有桶都满足需求时结束。

求达到了容量上限的桶的期望个数,答案对 998244353 取模。

1 \leq n \leq 250,\ 1 \leq b < a \leq 250

READ MORE

给定一个字符串 s,假设其 border 集合为 S,则每次你可以在 s 后面接上一个长度为 |s| - x 的字符串,其中 x \in S。问在总长度 \leq w 的情况下有多少种可能的本质不同的长度。

n \leq 5 \times 10^5,\ w \leq 10^{18}

READ MORE