忘了写题解，但总觉得要写点啥，所以就有了这篇题集。
忘了写题解，但总觉得要写点啥，所以就有了这篇题集。
首先，这道题是概率和期望分开算的，进行 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\)。
今天被各路神仙吊打，顺利 gg。
在考场上我推了个有后效性的 DP，还以为是高斯消元，然后看到数据范围就 GG 了。这道题主要是把一些东西给转换掉了。
首先，对一个概率为\(p\)的事件，它的期望次数是\(\frac{1}{p}\)（参见这里）。然后，考虑一个状态\(dp[i]\)代表合成第\(i\)级武器的期望花费。显然\(dp[0] = a\)。
考虑\(dp[1]\)的求法，首先需要两个级别为\(0\)的武器，然后发现无论失败与否都可以保证至少又一个\(0\)级武器，所以我们只需要注意另外一个武器的花费就可以了：
\[ dp[1] = dp[0] + dp[1] \times \frac{1}{p} \]
第一问比较好求，设状态\(f[i]\)为有\(i\)个叶子节点时的期望深度。考虑从上一个状态分裂会多对总深度做\(f[i-1]+2\)的贡献，可以知道：
\[ f[i] = \frac{f[i-1] * (i-1) + f[i-1] + 2}{i} = f[i-1] + \frac{2}{i} \]
一道概率期望类 DP。
我们设状态不考虑当前轮数：这样太难设计了，我太菜不会。考虑设计全局的状态：\(f[i][j]\)意义为考虑前\(i\)张卡牌，且游戏结束时只发动了\(j\)张纸牌的概率。那么答案就是：
这道题主要是运用贪心。首先我们可以确定以下几种情况是肯定无解的：
我们发现整个字符串\(s[1 \dots n]\)中，第一个和最后一个字符一定要是 ‘(‘ 和 ‘)’。所以我们只用关心\(s[2 \dots n-1]\)就好。统计需要补充的括号个数：也就是\((n-2)\)减去现已确定的括号个数，分\(remL\)为左括号需要补充的个数、\(remR\)为右括号需要补充的个数。