P3211:[HNOI2011]XOR和路径题解

主要思路

首先,这道题是概率和期望分开算的,进行 DP 时实质上是对概率进行 DP。考虑拆位,设\(dp_b [u]\)为从\(u \to n\)在第\(b\)位为\(1\)的概率,那么显然:

\[ dp_b[u] = \frac{1}{deg[u]}( \sum_{weight(u, v) !\& b} dp_b[v] \sum_{weight(u, v) \& b} (1 – dp_b[v]) ) \]

其中,\((1 – dp_b[v])\)为\(v\)为\(0\)的概率,最后答案消元完就是\(\sum_{i = 1} ans[i] 2^i\)。

继续阅读P3211:[HNOI2011]XOR和路径题解