两道概率题

玛里苟斯

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$ 时要求的是期望的平方, 即:
$$ \sum {i=0}^{32} \sum {j=0}^{32} b i b j 2 ^ {i+j} $$
其中 $ 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$ 的数量就变成一个经典问题了:

$$ E(S, T) = {|{(u, v) \in E | u \in S, v \in T)}|} $$

$$ F(S) = \sum _ {T \subset S, T \neq \varnothing} (-1) ^ {|T| - 1} \times 2 ^ {E(T, S-T)} F(T) $$

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

$$ F(S) = \sum {T \subset S, T \neq \varnothing} \sum {K = 1}^{|T|} (-1) ^ {K - 1} \times G _ K(T) \times 2 ^ {E(T, S-T) + E(S-T, S-T)} $$

$$ DP(S) = 2 ^ {E(S, S)} - F(S) $$

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

$$ P(S) = DP(S) + \sum _ {T \subset S, u \in T} - DP(T) \times P(S - T) $$

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

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