目录
THUWC + NOIWC + 过年完了，得滚回来打模拟赛了。
快要省选了哈哈。要寄大了。
WC 2024 游记 可能还是会持续更新的，毕竟讲的题整理没整理完代码也一个都没写，有点傻逼。
2024.2.15
100 / 100 / 20, sum 220, rk 12/98
我这波是致敬 WC。
R35 T2 弱化的杨表
简要题意：给定长为 \(n\) 的数组 \(a_i, b_i\)，对于一个长度为 \(n\) 的合法括号序列，一个位置填左括号的权值为 \(a_i\)，填右括号的权值为 \(b_i\)，这个括号序列的权值为每个位置的权值和，求合法括号序列的权值最小值。\(n \le 3 \times 10^5\)
赛时做法：考虑先让每个位置全部钦定权值较小的那个，然后尝试调整使得其变成合法括号序列。考虑合法两个条件：前缀和没有小于 \(0\) 的位置，且总和为 \(0\)。先调整第一个条件，从前往后考虑，碰到小于 \(0\) 的位置就在这个前缀中找到贡献最小的反转，每次这样会使得后缀和加 \(2\)。这样操作后就满足了第一个条件，考虑第二个条件，对于一个后缀最小值为 \(2\) 的位置，这之前最多只能进行一次操作，最小值为 \(4\) 的位置只能进行两次操作，那么我们找到最小值为 \(2,4,\cdots\) 的位置，在后缀中选一个最小值即可。
R35 T3 达拉然的废墟
简要题意贺的。
简要题意：\(T\) 组询问，每次给定 \(n,k\)，问：如果一个 \(2n\) 个数的排列所有偶数位置构成的子序列是单调递增的，那么说这个排列是好的。将一个好的排列按照顺序拆分成若干组，每一组个数都是偶数，形成的结构叫做一个城市。一个城市的价值是每个组内部的逆序对个数的乘积。求从所有城市中随机选取一个，它的代价的数学期望。\(T \le 10^4, k \le n \le 500\)
考虑题目可以轻松转换成在每一段中选取一对逆序对的方案数期望。分几种情况，显然不能都是偶数，那么就是奇奇，奇偶，偶奇。由于奇数位置没有限制，奇奇为逆序对的概率就是 \(\frac{1}{2}\)，但是因为偶数位置的限制，后面两种概率并不好计算。
考虑用大根堆来刻画这种大小关系，把偶数位置连成一条链，偶数递增就代表这棵树是大根堆，而对于一棵树是大根堆的概率为 \(\prod \frac{1}{size}\)，这个 ucup 某场有，懒得写了。那么我们用大根堆来刻画。那么对于偶奇的情况，相当于对应的偶数点下面挂一个叶子，对于奇偶的情况，我们容斥一下即可，用任意情况减去在偶数点下面挂一个叶子的概率。但是 \(\prod \frac{1}{size}\) 还是不好计算，注意到每个点下面最多挂一个叶子，也就是 \(size\) 之间的差值最多是 \(2\)，我们可以考虑记录一共挂了 \(k\) 个叶子，把没出现的 \(size\) 乘上，最后除以一个 \(\frac{1}{(n+k)!}\) 就行了。
那么设计 DP \(f_{i, j, k}\) 表示考虑前 \(2i\) 个点，共划分了 \(j\) 段的期望中，\(\frac{1}{(n+k)!}\) 的容斥系数和是多少，那么有：
\[\begin{aligned} f_{i, j, k} &= \frac 12 \sum_{l=0}^{i - 1} f_{l, j - 1, k} \frac{(i-l)(i-l-1)}{2} & \textsf{奇奇}\\ &+ \sum_{l=0}^{i - 1} f_{l, j - 1, k - 1} \sum_{p=l+1}^i (i-p) (p+k-1)& \textsf{偶奇}\\ &+ \sum_{l=0}^{i - 1} f_{l, j - 1, k} \sum_{p=l+1}^i (p-l) - \sum_{l=0}^{i - 1} f_{l, j - 1, k - 1} \sum_{p=l+1}^i (p-l) (p+k-1)& \textsf{奇偶}\\ \end{aligned} \]奇奇就是在中间选取两个点作为逆序对，概率为 \(\frac 12\)，偶奇就是枚举偶数的位置，然后在前面选取一个奇数的位置，由于在这里挂了一个叶子，这个子树的 \(size - 1\) 没有出现过，所以乘上 \(size - 1 = p + k - 1\)。奇偶前面是总方案数，后面是容斥。
注意到系数都是关于 \(l\) 的多项式，次数不超过 \(3\)，也就是说这个转移是 \(pre_{i, j, k, p} = \sum_{l = 0}^i f_{l, j, k} l^p\) 的线性组合，其中 \(0 \le p \le 3\)，那么我们就可以维护出这个 \(pre\)，然后就可以 \(O(1)\) 转移了，这样就是 \(O(n^3)\) 解决，需要卡常。
最后由于上面是对所有排列计算的，而题目要求的是所有合法排列的期望，合法排列方案数是 \(\binom{2n}{n} n! = \frac{(2n)!}{n!}\)，所以需要给答案乘上一个 \(n!\)。
标签：2024.2,le,frac,训练,sum,位置,偶数,权值,纪要 From： https://www.cnblogs.com/apjifengc/p/18016535