memset0's Notebook

咕

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

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。。。

给定 n 个整数 \langle a_1, a_2 ... a_n \rangle，在 [0; 2^m) 的范围内。对于 k \in [0; m]，求选出一个子集使得异或和的二进制表示有 k 个 1 的方案数。

1 \leq n \leq 2 \times 10^5,\ 0 \leq m \leq 53。

定义两个简单无向图 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。

给定三张 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)。