[THUPC2018]淘米神的树
先考虑开局只有一个黑点，将黑点做根，问有多少种排列满足父亲在儿子前。很平凡的问题，设\(f_u\)为\(u\)子树的合法序列个数，\(f_u=(siz_u-1)! \sum_{v \in son_u} \frac{f_v}{siz_v!}\)，先将根放入，再由合法子树相对序列代替全排列。整理答案为\(ans=\frac{\prod_u (siz_u-1)!}{\prod_{u \neq rt} siz_u!}=\frac{n!}{\prod_u siz_u}\)。
再考虑两个黑点，建一个虚点为根，连上两个黑点,一开始虚点为黑点，一此操作后，a,b为黑点，与原问题等价。现在树成为基环树。枚举删除一条环上的边的答案，当环上的某点作为环上最后一个染黑的点会在断左边边和断右边边中重复出现，答案要乘\(\frac{1}{2}\)。
处理出除环上点的子树大小，给环上点重编号，虚点是0，其他点一次是1~k，设\(a_u\)是环上u点的除了环上儿子的子树大小，\(b_u\)是断掉i->i+1边后的子树大小。有
\[b_u=\begin{cases} \sum_{j=1}^u a_j & 1 \le u\le i \\ \sum_{j=u}^k a_j & i+1\le u\le k \end{cases}\]对a做前缀和为c
\[\prod_u b_u=\prod_{u=0,u \neq i} |c_u-c_i| \]可多项式快速插值，时间复杂度\(O(nlog^2n)\)
Mergesort Strikes Back
题意
一个长度为\(n\)的随机排列，进行深度为\(k\)的归并排序（\([1\dots n]\)为第一层），求期望逆序对个数。
题解
首先考虑对两个序列归并，找到比前位所有元素的大的元素，一次为分块开头，对每个块以开头元素的大小排序。而对归并k层分成的\(2^{k-1}\)个片段来说，同样。在每个片段中，合并时的相对顺序保持不变，因此它们所贡献的期望逆序对个数只是\(\frac{l(l-1)}{4}\)（对于长度为l的片段），可以看作枚举两个点，前大于后与后大于前的概率相同，那么前大于后形成逆序对的概率是\(\frac{1}{2}\)。
再次假设每个片段都被划分成前面提到的块，我们只是按照开头的元素对这些块进行排序。让我们考虑由两个不同段中的两个块形成的逆序对。假设形成逆序对的元素是各自片段中的第i个和第j个，考虑这i+j数中的最大值 ，如果它是这两个元素中的一个，就不能形成逆序对。最大值既不是i也不是j的概率是\(\frac{i+j-2}{i+j}\)，i和j的大小顺序与两个块开头最大值的大小顺序不同的概率为\(\frac{1}{2}\)，那么i，j形成逆序对的概率为\(\frac{i+j-2}{2(i+j)}=\frac{1}{2}-\frac{1}{i+j}\)。
再预处理一些东西，可以在\(O(n)\)的时间计算两个片段的答案，又有结论片段的长度取值最多2个，答案又只与段长对有关，所以全部答案可得。
标签：片段,Set,frac,环上,黑点,Solution,prod,杂题,逆序 From： https://www.cnblogs.com/yswn/p/18150381