Permutation Blackhole
按照过题人数顺序做题是这样的，如果要看难一点的建议向下
首先，不要读错题 QAQ
然后你现在发现每个位置只会在它被涂黑之前向最近放位置产生一次贡献，从 P 的角度思考是困难的，考虑从被涂黑的图的角度思考
你注意到我们每次涂完两个点之后，它们中间的点就不会在被外面的点贡献到，也不会对外面的点产生贡献，变成了完全独立的子问题
因此我们考虑区间 DP。我们发现，只要我们钦定一个区间两头的点已经被放了，那么看起来就很对。
但是很坏的一点是，我们无法做到正常的往两侧的点转移。
但是你思考然后就会发现，一个点的答案是 O(logn) 级别的，因此我们可以直接记录向两侧的转移。
然后你再精细分析一下，对于 -1 的我们可以全维护到 0 上，然后其他的 \(\sum\) 是 O(n) 的，因此是好做的，我们时间可以分析到 \(O(n^3)\) 级别。（有几个 \(n^2logn\)），空间使用 vector 可以轻松做到 \(O(n^2)\)，但我是懒狗，所以空间写的 \(O(n^2log^2n)\)
Sum of SCC
首先根据竞赛图的性质一的推论，我们转化为对划分方案的计数。
这个划分方案是好计数的，你考虑每次新增一个点它加入集合的方案就好了
Random Isolation
Isolation~~ is not good for me~~~
Isolation~~ I don't want to~~……
Trick1：我们可以将 从所有属于某个包含至少 \(K+1\) 个顶点的连通分量的顶点中，等概率随机选择一个顶点 转化为 对于一个随机的长度为 \(n\) 的排列 \(p\)，我们按照 \(p_1,p_2,\dots, p_n\) 的顺序考虑，如果符合条件就删去这个点
证明：（！！！感性至极！！！）
首先我们考虑一个中间状态 \(A\)，现在我们还能选的点集为 \(S\)，如果按照原题意，那么现在我们应当是在这 \(|S|\) 个节点里等概率随机一个节点。
而按照我们更新的题意，首先我们知道这 \(|S|\) 个点一定都是在现在还没枚举到的后面的，然后因为是等概率随机的一个排列，所以每个点都是等价的，因此概率一定均等。\(\Box\)
好的，现在我们有了这个 Trick，我们可以分析一下题面了。
考虑期望的线性性，我们尝试将每个点的贡献拆开计算。但是你发现这是极其困难的，非常依赖于我们现在这个图的形态，难以做到。
然后我们考虑这个贡献是否可以拆到其他东西上。
然后你惊喜地发现，任意 \(siz>k\) 的连通块每出现一次，就代表着 \(1\) 的贡献。
也就是说，贡献还可以被划分到连通块上。
然后我们使用期望的线性性，于是现在问题就变成了：对于一个连通块，求其出现的期望。
然后我们去观察一个连通块，考察其性质，结合 Trick1，容易发现，最终其出现的概率等价于其相连的所有节点都排在它的节点之前的概率。
具体的，设当前选择的连通块的大小为 \(a\)，其向外连了 \(b\) 条边，它在最终序列里出现的概率就等于 \(\dfrac{a!b!}{(a+b)!}\)
现在我们剩下的就只有求出每种大小、向外连边数相等的连通块有多少个了。
使用树上背包可以很好的解决问题。
相关题目：Removing Gacha
在做上面那道题的时候看到的，于是写一下
注意这个题不是 DP 了，也不是题单里的题
首先我们考虑部分延续上面那道题的思路，考虑将“每次选择一个坏点”转化为“每次选一个点，如果是坏点贡献+1，否则贡献不变”
这样做的好处是什么呢？是我们在拆分每个点的贡献的时候，就可以不必在意非其祖先的点产生的贡献了，也就是说，我们现在每次随机到我们想要的点的概率不再受到其它的点的限制，而是成为了一个定值.
因此考虑期望的线性性，我们尝试拆分为每个点期望产生多大的贡献
首先，由于其它的点不再对
我们发现，因为每次选择的概率都是一样的，所以这个点产生的贡献，就是其到不能贡献时原序列选点的次数乘 \(\dfrac{1}{d_i}\)
然后考虑不能贡献的时刻是什么时候，显然是当所有祖先都被选过至少一次的时候
然后你注意到祖先间在此时是没有区别的，于是就变成了在一个点集里随机选点，求选完时间的期望
注意到这里正确的下一步是算选到一个新点的期望，而不是对于每个点分别看，因为你注意到如果你分开看，就会忽视掉在你这个选择过程中被选的那些点中是否有未选的点，也就是说这个不独立。
假设已经选了 \(k\) 个点，选到一个新点的概率是 \(\dfrac{d_i-k}{d_i}\)，所以选到一个新点次数的期望是 \(\dfrac{d_i}{d_i-k}\)
现在稍微推一下式子：
代码就很唐了
从这道题可以粗略看出，如果这道题涉及一些可能无尽的操作，通常需要至少 swap 一次分子分母
Highest
一开始看的时候总觉得是倍增板子，然后思索一道倍增板子是怎么放到 DP 专题里的？令人忍俊不禁。
后来经过审慎地思考，发现会出现一些奇妙情况，即考虑转移时我们不一定是从最后一个点转移过去的，还可能是从倒数第二个点转移过去的。
然而在我们正常的倍增流程里，我们直接选择了最后一个点进行转移，因此就彻底倒闭了。
然后我们思考如何拯救它。
然后你发现这个思考是简单的，因为我们每次做这个选择的时候前面的倍增数组都做好了，所以我们可以直接干脆找到那个对应的点，然后用 log 的时间转移。
因为我们一共要转移 O(nlogn) 次，因此复杂度是 \(O(n\log^2n)\) 的
但是你观察它的部分分，能明显感觉到它最后两档期望的是你用单 log 的时间做到
然后你再次进行一个审慎的思考，然后你惊喜的发现，小一步的那个东东它的转移是显然的。
那么你先转移小一步的那个东东，然后就能轻松做到 O(nlogn) 了
这里需要注意的是，通过贪心，我们每次要到达的点是 i+v/w_i 最大的点之一