两道概率题

玛里苟斯

Description

给你一个大小为N的可重集合, 求该集合子集异或和的$K$次方的期望, 保证答案不超过$2 ^ {64}$.

$N \le 100000, K \le 5, A _ i \le 10 ^ 9$

Solution

   $K=1$ 时满足期望的线性性, 可以对每一个二进制位分开计算答案. 不难发现每一个二进制位变成 $1$ 的概率恰好为 $\frac {1}{2}$ (集合的奇数和偶数大小的子集数相同).

   $K=2$ 时要求的是期望的平方, 即:

其中 $b_i$表示期望二进制第 $i$ 位的值, 枚举两个二进制位再求一下两个位置同时取到 $1$ 的概率即可.

   $K \ge 3$时由于答案不超过 $2^{64}$, 所以集合内的数也不会很大, 直接用线性基处理.

主旋律

Description

求N个点, M条边的有向图有多少生成子图满足整个图是强联通的.

$N \le 15, M \le N(N-1)$

Solution

   这题一眼看上去不太好做, 不妨从问题的反面来考虑. 首先一个非强联通的图缩掉$Scc$ 之后会得到若干个 $DAG$. 如果知道$Scc$ 的划分情况, 计算$DAG$ 的数量就变成一个经典问题了:

   然而感觉枚举$Scc$ 划分更不可做. 先不考虑$Scc$ 如何划分, 考虑哪一些点集构成多少个$Scc$. 假设$G _ K(T)$表示$T$ 集合分成$K$ 个$Scc$ 的方案数, 类似上面式子地, 有:

   实际上只需要求将某个集合分成奇数个$Scc$ 与偶数个$Scc$ 的方案数之差 $P(S)$:

其中 $u \in T$ 避免重复计数.

   这样加上一些预处理的技巧可以做到 $O(3 ^ n)$.