前言
本文章主要用作 qhy 的自我复习，读者可以适当参考，若有读不懂的部分，可能是因为 qhy 语言过于自我化，建议食用其它题解为佳，因为 qhy 自身水平有限，可能会有部分言语欠妥之处，若读者有发现，可以在评论区指出。
另外，本文持续更新，尽量不咕。
仓鼠找 sugar II
好激动啊我竟然自己推出来了。
答案就是所有方案数的步数和 $\times inv[n]^2$，因此我们需要求方案数。
这种在树上求贡献的题一般就考虑每条边所能带来的贡献就可以了。
我们指定 $1$号节点为根，注意到向上走和向下走的期望显然是不一样的，我们考虑计算每个点走到根节点的期望步数 $e1[u]$和根节点到每个点的期望步数 $e2[u]$。
令 $fa$为 $u$的父节点，$d$为 $u$的度数
$$e1[u]=\frac 1 d (e1[fa] + \sum_{v \in son[u]}e1[v]) + 1$$
你会发现这东西从上到下 dp 也不是，从下到上 dp 也不是。
考虑改变方程含义，一种常见的搞法是 $e1[u]$表示 $u$到父节点的期望步数，$e2[u]$表示父节点到 $u$的期望步数 (这里因为每个点只有唯一的父节点，因此这样设计状态，读者可以尝试 $e2[u]$表示 $u$到子节点的期望步数，来比较这两种状态设计的优劣)
$$e1[u]=(\frac1 d\sum_{v\in son[u]} e1[v] + e1[u]) + 1$$
化简
$$e1[u] = d + \sum_{v \in son[u]} e1[v]$$
从下往上跑一次即可
$e2$同理，记 $d$为父节点 $fa$的度数 (这里我们假设 $fa[u]$不是根节点，事实上在实现的时候只需要将 $e2[1]=0$即可)
$$e2[u] = 1 + \frac 1 d(e2[fa] + e2[u]]) + \frac 1 d\sum_{v \in son[fa]\v \ne u} (e1[v]+e2[u])$$
化简
$$e2[u] = d + e2[fa] + \sum_{v \in son[fa] \ v \ne u} e1[v]$$
从上往下跑一次即可，最后一项可以维护一个 $u$的子节点的 $e1$和 $es$
每条边的贡献就是 $$(e1[u] + e2[u]) \times (sz[1] – sz[u]) \times sz[u]$$
[SHOI2012] 随机树
正着做很难做，我们考虑倒着来。假设你有很多点组成的森林，每一次挑一棵只有一个点的树，然后将两棵树连在这个点的两边，完成一次逆展开 (合并)。
先考虑第一问
我们发现每一次逆展开一个节点，两棵树内所有叶子节点深度+1，我们记 $f[n]$表示 n 个叶子节点的树的期望叶子节点平均深度，那么
$$f[n]=\sum_{i=1}^{n-1}(f[i]+f[n – i]+n)=[2(\sum_{i=1}^{n-1}f[i]) + n(n-1)]/i$$
用个 $sum$和维护一下 $\sum$就可以了
第二问也用类似的思想，因为对答案有贡献的是两棵子树中深度更大的那个，你不可能直接用它们的期望深度来转移，所以设 $f[i][j]$表示 $i$个叶子节点的树深度为 $j$的方案数，枚举第一个子树的叶子节点个数 $k$，第二个字数的叶子节点个数就是 $i-k$，我们有
$$f[i][j] = \sum f[k][j1]\times f[i-k][j2]\quad(max{j1,j2}=j)$$
根据乘法分配率，我们可以维护一下 $f[i]$的前缀和，可以将上述转移优化到 $O(1)$
但是，是不是还缺了什么？
你在合并树的时候，要考虑到子树合并起来的所用步数，显然有 $n$个叶子的子树合并起来要 $n-1$步，那么叶子节点个数分别为 $k$和 $i-k$的两个子树合并，可以有 $C_{i-2}^{k – 1}$种方案数，于是上面的转移方程只需要乘上这个组合数即可。
然后喜题 $80$分，很明显的原因是 $n$大的时候组合数巨大，精度炸了。
我们可以这样做，$f[i][j]$表示深度 $\geq j$的概率
$$f[i][j] = \frac{\sum_{k=1}^{i-1} f[k][j] + f[i-k][j] – f[k][j] \times f[i-k][j]} { (i-1)}$$
并不太能感性理解为什么这样做能规避组合数，只能说考试的时候多想想前缀和容斥方面的东西吧
[JXOI2018] 游戏
呜呜呜这道题我没想到最基本的一点导致无处下手，最后只能去看题解爬。
注意到总有一部分基础数，如果它们不被选，它们就永远不会因为是某些数的倍数的原因而被选，然后就是简单的组合问题了。
不想多解释，因为知道上面这一点很容易推出公式。
我通过这道题联想到了 CCPC Training Class
虽然结论很好猜，是出现次数最多的字母的出现次数 $k$，但是我并没有想到根据定义可以知道 $k$就是上界，证明也很简单，每一次答案的+1 意味着两个相等的串的末尾字符相同，因此 $k$就是上界，这种比较巧妙的证明我并不太熟悉，所以要多注意了 $QwQ$
CF1418E Expected Damage
显然我们可以将攻击力根据是否 $\geq b$分成两类，记大的那类有 $cnt$个。
我先考虑的方法是记每个数对总答案的贡献
我们先将大的 $cnt$个数乱排序，排在前面的 $a$个数没有贡献，那么每个数的贡献就是 $(cnt – 1)!(cnt-a)$
然后考虑将小的数插入其中，注意到有 $cnt+1$个空，前 $a$个空是没有贡献的，因此我们稍加考虑，每个数的贡献是 $(cnt+1-a)(cnt+1)^{n – cnt-1}$
你很容易发现这种做法咕咕咕了，因为如果一个空位里有大于 1 个数的话，方案数还要进一步计算，但是你会发现你并不会如何算。
至此 qhy 就卡住了，然后就去看了题解。
题解直接用概率来算了，对于小的数，每一个数 $t$插入 $cnt+1$个空中造成的期望贡献是 $\frac{cnt+1-a}{cnt+1}t$，根据期望的线性性，我们就知道了所有小数的期望贡献是 $\frac{cnt+1-a}{cnt+1}\sum_{t \in small} t$
大数也可以用类似的方法，这里就不展开来讲了。
所以快点想起来期望有线性性！
SHOI2014 概率充电器
写了个假的代码，然后看了题解
首先注意到，每个灯亮的贡献是 $1$，答案即为每个灯亮的概率和。
注意到，一个灯亮，当且仅当它自己亮或者在自己不亮的前提下至少有一个连接的灯亮并且对应线是能导电的，这个至少一个的条件就很糟糕，因此我们考虑反面，求每个灯不亮的概率。
已知每个灯亮的概率是 $q_i$，每条边导电的概率是 $e_{u,v}$
我们先记 $f_u$表示 $u$在 $u$所在子树 (包括它本身) 影响下，不亮的概率。
$$f_u = (1-q_u)\prod_{v \in son_u}(e_{u,v}\times f_v + 1-e_{u,v})$$
定根为 1，自底向上 dfs 一遍。记 $p_u$表示 $u$不亮的概率。
容易知道，$p_1=f_1$，但是因为其它点并不知道它们会不会被父节点点亮，所以我们还要进一步计算。
记 $g_u$表示 $u$点不被父节点 $fa$点亮的概率。
$$g_u=(1-e_{fa,u})+e_{fa,u} \times p_{fa}$$
看似是这样，实则不然，我们的 $p_{fa}$是考虑过 $fa$不被 $u$点亮的情况的，记事件 $A$表示 $fa$不亮，事件 $B$表示 $fa$不被 $u$点亮，那么由条件概率公式
$$P(A|B)=\frac {P(AB)}{P(B)}$$
因为 $A \subseteq B$
$$P(AB)=P(A)=p_{fa}$$
$$P(B)=f_{u}\times e_{fa,u} + 1 – e_{fa,u}$$
把 $P(A|B)$替换上面算 $g_u$中的 $p_{fa}$即可。
$$p_u=g_u \times f_u$$
自根向下再 dfs 一次就能求出所有的 $p_u$，答案就是 $\sum{1-p_u}$
顺便，当心除数为 0 的情况，注意特判。
0 条评论